[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

Dynamic Cycles in Edge-Colored Multigraphs

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

Let H be a graph possibly with loops and G be a multigraph without loops. An H-coloring of G is a function \(c: E(G) \rightarrow V(H)\). We will say that G is an H-colored multigraph, whenever we are taking a fixed H-coloring of G. The set of all the edges with end vertices u and v will be denoted by \(E_{uv}\). We will say that \(W=(v_0,e_0^1, \ldots , e_0^{k_0},v_1,e_1^1,\ldots ,\) \(e_1^{k_1},v_2,\ldots ,v_{n-1},e_{n-1}^1,\ldots ,e_{n-1}^{k_{n-1}},v_n)\), where for each i in \(\{0,\ldots ,\) \(n-1\}\), \(k_i \ge 1\) and \(e_i^j \in E_{v_iv_{i+1}}\) for every \(j \in \{1,\ldots , k_i \}\), is a dynamic H-walk iff \(c(e_i^{k_i})c(e_{i+1}^1)\) is an edge in H, for each \(i \in \{0,\ldots ,n-2\}\). We will say that a dynamic H-walk is a closed dynamic H-walk whenever \(v_0=v_n\) and \(c(e_{n-1}^{k_{n-1}})c(e_0^1)\) is an edge in H. Moreover, a closed dynamic H-walk is called dynamic H-cycle whenever \(v_i\ne v_j\), for every \(\{i,j\}\subseteq \{0,\ldots ,v_{n-1}\}\). In particular, a dynamic H-walk is an H-walk whenever \(k_i=1\), for every \(i \in \{0,\ldots ,n-1\}\), and when H is a complete graph without loops, an H-walk is well known as a properly colored walk. In this work, we study the existence and length of dynamic H-cycles, dynamic H-trails and dynamic H-paths in H-colored multigraphs. To accomplish this, we introduce a new concept of color degree, namely, the dynamic degree, which allows us to extend some classic results, as Ore’s Theorem, for H-colored multigraphs. Also, we give sufficient conditions for the existence of hamiltonian dynamic H-cycles in H-colored multigraphs, and as a consequence, we obtain sufficient conditions for the existence of properly colored hamiltonian cycle in edge-colored multigraphs, with at least \(c\ge 3\) colors.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

  1. Bang-Jensen, J., Gutin, G.Z.: Digraphs: Theory, Algorithms and Applications. Springer, London (2009). https://doi.org/10.1007/978-1-84800-998-1

  2. Bondy, J.A., Murty, U.S.R.: Graph Theory With Applications. The Macmillan Press Ltd., London (1976)

    Book  MATH  Google Scholar 

  3. Bang-Jensen, J., Bellitto, T., Yeo, A.: On supereulerian 2-edge-coloured graphs. Graphs Combin. 37(6), 2601–2620 (2021). https://doi.org/10.1007/S00373-021-02377-8/METRICS

    Article  MathSciNet  MATH  Google Scholar 

  4. Barát, J., Sárközy, G.N.: Partitioning 2-edge-colored ore-type graphs by monochromatic cycles. J. Graph Theory 81(4), 317–328 (2016). https://doi.org/10.1002/JGT.21877

    Article  MathSciNet  MATH  Google Scholar 

  5. Guo, Z., Broersma, H., Li, B., Zhang, S.: Almost eulerian compatible spanning circuits in edge-colored graphs. Discrete Math. 344(1), 112174 (2021). https://doi.org/10.1016/J.DISC.2020.112174

    Article  MathSciNet  MATH  Google Scholar 

  6. Guo, Z., Li, B., Li, X., Zhang, S.: Compatible spanning circuits in edge-colored graphs. Discrete Math. 343(7), 111908 (2020). https://doi.org/10.1016/J.DISC.2020.111908

    Article  MathSciNet  MATH  Google Scholar 

  7. Dorninger, D.: Hamiltonian circuits determining the order of chromosomes. Discrete Appl. Math. 50(2), 159–168 (1994). https://doi.org/10.1016/0166-218X(92)00171-H

    Article  MathSciNet  MATH  Google Scholar 

  8. Dorninger, D., Timischl, W.: Geometrical constraints on Bennett’s predictions of chromosome order. Heredity 59(3), 321–325 (1987). https://doi.org/10.1038/hdy.1987.138

    Article  MATH  Google Scholar 

  9. Szachniuk, M., Popenda, M., Adamiak, R.W., Blazewicz, J.: An assignment walk through 3D NMR spectrum. 2009 IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology, CIBCB 2009 - Proceedings, pp. 215–219 (2009). https://doi.org/10.1109/CIBCB.2009.4925731

  10. Chou, W.S., Manoussakis, Y., Megalakaki, O., Spyratos, M., Tuza, Z.: Paths through fixed vertices in edge-colored graphs. Math. Inform. Sci. Humaines 127, 49–58 (1994)

    MathSciNet  MATH  Google Scholar 

  11. Ahuja, S.K.: Algorithms for routing and channel assignment in wireless infrastructure networks, PhD thesis, The University of Arizona (2010)

  12. Sankararaman, S., Efrat, A., Ramasubramanian, S., Agarwal, P.K.: On channel-discontinuity-constraint routing in wireless networks. Ad Hoc Networks 13(PART A), 153–169 (2014). https://doi.org/10.1016/J.ADHOC.2011.04.011

  13. Chetwynd, A.G., Hilton, A.J.W.: Alternating hamiltonian cycles in two colored complete bipartite graphs. J. Graph Theory 16(2), 153–158 (1992). https://doi.org/10.1002/JGT.3190160206

    Article  MathSciNet  MATH  Google Scholar 

  14. Feng, J., Giesen, H.E., Guo, Y., Gutin, G., Jensen, T., Rafiey, A.: Characterization of edge-colored complete graphs with properly colored Hamilton paths. J. Graph Theory 53(4), 333–346 (2006). https://doi.org/10.1002/JGT.20188

    Article  MathSciNet  MATH  Google Scholar 

  15. Lo, A.: A Dirac type condition for properly coloured paths and cycles. J. Graph Theory 76(1), 60–87 (2014). https://doi.org/10.1002/JGT.21751

    Article  MathSciNet  MATH  Google Scholar 

  16. Lo, A.: Long properly coloured cycles in edge-coloured graphs. J. Graph Theory 90(3), 416–442 (2019). https://doi.org/10.1002/JGT.22405

    Article  MathSciNet  MATH  Google Scholar 

  17. Grossman, J.W., Häggkvist, R.: Alternating cycles in edge-partitioned graphs. J. Combin. Theory Ser. B 34(1), 77–81 (1983). https://doi.org/10.1016/0095-8956(83)90008-4

    Article  MathSciNet  MATH  Google Scholar 

  18. Yeo, A.: A note on alternating cycles in edge-coloured graphs. J. Combin. Theory Ser. B 69(2), 222–225 (1997). https://doi.org/10.1006/JCTB.1997.1728

    Article  MathSciNet  MATH  Google Scholar 

  19. Abouelaoualim, A., Das, K.C., Vega, W.F.D.L., Karpinski, M., Manoussakis, Y., Martinhon, C.A., Saad, R.: Cycles and paths in edge-colored graphs with given degrees. J. Graph Theory 64(1), 63–86 (2010). https://doi.org/10.1002/JGT.20440

    Article  MathSciNet  MATH  Google Scholar 

  20. Linek, V., Sands, B.: A note on paths in edge-coloured tournaments. ARS Combin. 44, 225–228 (1996)

    MathSciNet  MATH  Google Scholar 

  21. Delgado-Escalante, P., Galeana-Sánchez, H., Ramírez, L.P.: Independent restricted domination and the line digraph. AKCE Int. J. Graphs Combin. 9(1), 31–42 (2012). https://doi.org/10.1080/09728600.2012.12088947

    Article  MathSciNet  MATH  Google Scholar 

  22. Delgado-Escalante, P., Galeana-Sánchez, H.: Restricted domination in arc-colored digraphs. AKCE Int. J. Graphs Combin. 11(1), 95–104 (2014). https://doi.org/10.1080/09728600.2014.12088766

    Article  MathSciNet  MATH  Google Scholar 

  23. Galeana-Sánchez, H., Sánchez-López, R.: H-kernels in infinite digraphs. Graphs Combin. 29(4), 913–920 (2013). https://doi.org/10.1007/S00373-012-1150-6/METRICS

    Article  MathSciNet  MATH  Google Scholar 

  24. Galeana-Sánchez, H., Rojas-Monroy, R., Sánchez-López, R., Villarreal-Valdés, J.I.: Some conditions for the existence of Euler H-trails. Graphs Combin. 35(5), 1197–1208 (2019). https://doi.org/10.1007/S00373-019-02066-7/METRICS

    Article  MathSciNet  MATH  Google Scholar 

  25. Galeana-Sánchez, H., Rojas-Monroy, R., Sánchez-López, R., Villarreal-Valdés, J.I.: H-cycles in H-colored multigraphs. Graphs Combin. 38(3), 1–20 (2022). https://doi.org/10.1007/S00373-022-02464-4/METRICS

    Article  MathSciNet  MATH  Google Scholar 

  26. Benítez-Bobadilla, G., Galeana-Sánchez, H., Hernández-Cruz, C.: Characterization of color patterns by dynamic H-paths. Discrete Appl. Math. 267, 41–51 (2019). https://doi.org/10.1016/J.DAM.2019.04.020

    Article  MathSciNet  MATH  Google Scholar 

  27. Farr, E.R., Stoll, J.S., Beitl, C.M.: Effects of fisheries management on local ecological knowledge. Ecol. Soc. 23(3) (2018). https://doi.org/10.5751/ES-10344-230315

  28. Shafie, T., Schoch, D.: Multiplexity analysis of networks using multigraph representations. Stat. Methods Appl. 30(5), 1425–1444 (2021). https://doi.org/10.1007/S10260-021-00596-0/FIGURES/9

    Article  MathSciNet  MATH  Google Scholar 

  29. Shafie, T.: A multigraph approach to social network analysis. J. Soc. Struct. 16 (2015). https://doi.org/10.21307/JOSS-2019-011

Download references

Acknowledgements

The authors wish to emphatically thank the anonymous referees for their thorough review.

Funding

This research was supported by CONACYT FORDECYT-PRONACES/39570/2020, UNAM DGAPA-PAPIIT IN102320 (H. Galena-Sánchez), and CONACYT scholarships for postgraduate studies 782239 (C. Vilchis-Alfaro).

Author information

Author notes

  1. Hortensia Galeana-Sánchez and Carlos Vilchis-Alfaro contributed equally to this work.

Authors and Affiliations

  1. Instituto de Matemáticas, Universidad Nacional Autónoma de México, Área de la Investigación Científica, Circuito Exterior, Ciudad Universitaria, Coyoacán, 04510, Mexico City, Mexico

    Hortensia Galeana-Sánchez & Carlos Vilchis-Alfaro

Authors
  1. Hortensia Galeana-Sánchez
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Carlos Vilchis-Alfaro
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Carlos Vilchis-Alfaro.

Ethics declarations

Conflict of interest

We have no conflict of interest to disclose.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Galeana-Sánchez, H., Vilchis-Alfaro, C. Dynamic Cycles in Edge-Colored Multigraphs. Graphs and Combinatorics 41, 2 (2025). https://doi.org/10.1007/s00373-024-02868-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s00373-024-02868-4

Keywords

Mathematics Subject Classification

Search

Navigation