DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2023): 0.5

5-year Journal Impact Factor (2023): 0.6

CiteScore (2023): 2.2

SNIP (2023): 0.681

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

J. Fiala

Jiří Fiala

Charles University

email: fiala@kam.mff.cuni.cz

0000-0002-8108-567X

M. Seifrtová

Michaela Seifrtová

Charles University

email: kukuckaa@gmail.com

Title:

A novel approach to covers of multigraphs with semi-edges

PDF

Source:

Discussiones Mathematicae Graph Theory 45(2) (2025) 451-481

Received: 2023-02-28 , Revised: 2024-01-25 , Accepted: 2024-01-26 , Available online: 2024-02-15 , https://doi.org/10.7151/dmgt.2540

Abstract:

We present three equivalent models for graphs and their covers, two of which are applicable to more general structures such as mixed colored directed multigraphs with semi-edges. In this context, we extend the concept of equitable and degree partitions, and provide efficient algorithms for their calculation. We demonstrate that the dart model introduces simpler concepts. Leveraging this model, we introduce a novel notion of the degree matrix for the general graph model. Additionally, we reassert and expand upon Leighton's theorem regarding the existence of a finite common cover for graphs containing semi-edges.

Keywords:

graph coverings, topological graph theory

References:

  1. J. Abello, M.R. Fellows and J.C. Stillwell, On the complexity and combinatorics of covering finite complexes, Australas. J. Combin. 4 (1991) 103–112.
  2. D. Angluin, Local and global properties in networks of processors, in: Proc. 12th ACM Symposium on Theory of Computing (1980) 82–93.
    https://doi.org/10.1145/800141.804655
  3. D. Angluin and A. Gardiner, Finite common coverings of pairs of regular graphs, J. Combin. Theory Ser. B 30 (1981) 184–187.
    https://doi.org/10.1016/0095-8956(81)90062-9
  4. N. Biggs, Algebraic Graph Theory (Cambridge University Press, 1974).
    https://doi.org/10.1017/CBO9780511608704
  5. H.L. Bodlaender, The classification of coverings of processor networks, J. Parallel Distrib. Comput. 6 (1989) 166–182.
    https://doi.org/10.1016/0743-7315(89)90048-8
  6. J. Bok, J. Fiala, P. Hliněný, N. Jedličková and J. Kratochvíl, Computational complexity of covering multigraphs with semi-edges: Small cases, in: 46th International Symposium on Mathematical Foundations of Computer Science, LIPIcs, Leibniz Int. Proc. Inform. 202, F. Bonchi and S.J. Puglisi (Ed(s)), (Dagstuhl Publishing, Germany 2021) 21:1–21:15.
    https://doi.org/10.4230/LIPIcs.MFCS.2021.21
  7. P. Boldi and S. Vigna, Fibrations of graphs, Discrete Math. 243 (2002) 21–66.
    https://doi.org/10.1016/S0012-365X(00)00455-6
  8. D.G. Corneil, Graph Isomorphism, PhD Thesis (University of Toronto, 1968).
  9. D.G. Corneil and C.C. Gotlieb, An efficient algorithm for graph isomorphism, J. ACM 17 (1970) 51–64.
    https://doi.org/10.1145/321556.321562
  10. D.M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs, Theory and Applications, Revised Version (Huthing Pub. Ltd, 1995).
  11. J.R. Edmonds, A Combinatorial Representation for Oriented Polyhedral Surfaces, PhD Thesis (University of Maryland, 1960).
    https://doi.org/10.13016/daw5-mvla
  12. J. Fiala, P. Klavík, J. Kratochvíl and R. Nedela, Algorithmic aspects of regular graph covers with applications to planar graphs, in: Automata, Languages, and Programing, Lecture Notes in Comput. Sci. 8572, J. Esparza, P. Fraigniaud, T. Husfeldt and E. Koutsoupias (Ed(s)), (Springer, Berlin, Heidelberg 2014) 489–501.
    https://doi.org/10.1007/978-3-662-43948-7_41
  13. J. Fiala and J. Kratochvíl, Partial covers of graphs, Discuss. Math. Graph Theory 22 (2002) 89–99.
    https://doi.org/10.7151/dmgt.1159
  14. J. Fiala and J. Kratochvíl, Locally constrained graph homomorphisms–-structure complexity, and applications, Comput. Sci. Rev. 2 (2008) 97–111.
    https://doi.org/10.1016/j.cosrev.2008.06.001
  15. J. Fiala, D. Paulusma and J.A. Telle, Locally constrained graph homomorphisms and equitable partitions, European J. Combin. 29 (2008) 850–880.
    https://doi.org/10.1016/j.ejc.2007.11.006
  16. J.L. Gross and T.W. Tucker, Generating all graph coverings by permutation voltage assignments, Discrete Math. 18 (1977) 273–283.
    https://doi.org/10.1016/0012-365X(77)90131-5
  17. J.L. Gross and T.W. Tucker, Topological Graph Theory (Dover Publications, INC, Mineola, New York, 1987).
  18. A. Grothendieck, Technique de descente et théorèmes d'existence en géométrie algébrique. I: Généralités. Descente par morphismes fidèlement plats, Séminaire N. Bourbaki 5 (1960) 299–327.
    http://www.numdam.org/item?id=SB_1958-1960__5__299_0
  19. B. Jackson, T.D. Parsons and T. Pisanski, A duality theorem for graph embeddings, J. Graph Theory 5 (1981) 55–77.
    https://doi.org/10.1002/jgt.3190050104
  20. G.A. Jones and D. Singerman, Theory of maps on orientable surfaces, Proc. Lond. Math. Soc. 37(3) (1978) 273–307.
    https://doi.org/10.1112/plms/s3-37.2.273
  21. D. König, Theorie der endlichen und unendlichen Graphen: Kombinatorische Topologie der Streckenkomplexe (Akademische Verlagsgesellschaft, Leipzig, 1936).
  22. J. Kratochvíl, A. Proskurowski and J.A. Telle, Complexity of colored graph covers I. Colored directed multigraphs, in: Graph-Theoretic Concepts in Computer Science, Proc. 23 WG'97, Lecture Notes in Comput. Sci. 1335, (Springer, Berlin Heidelberg 1997) 242–257.
    https://doi.org/10.1007/BFb0024502
  23. J. Kratochvíl, A. Proskurowski and J.A. Telle, Covering directed multigraphs II. When 2-SAT helps (Tech. Rep. 1997–354 {KAM-DIMATIA} Preprint Series, 1997).
  24. J. Kratochvíl, A. Proskurowski and J.A. Telle, Covering regular graphs, J. Combin. Theory Ser. B 71 (1997) 1–16.
    https://doi.org/10.1006/jctb.1996.1743
  25. J. Kratochvíl, A. Proskurowski and J.A. Telle, Complexity of graph covering problems, Nordic J. Comput. 5 (1998) 173–195.
  26. F.T. Leighton, Finite common coverings of graphs, J. Combin. Theory Ser. B 33 (1982) 231–238.
    https://doi.org/10.1016/0095-8956(82)90042-9
  27. A. Malnič, R. Nedela and M. Škoviera, Lifting graph automorphisms by voltage assignments, European J. Combin. 21 (2000) 927–947.
    https://doi.org/10.1006/eujc.2000.0390
  28. A.D. Mednykh and R. Nedela, Harmonic Morphisms of Graphs: Part I: Graph Coverings (Vydavatelstvo Univerzity Mateja Bela v Banskej Bystrici, 2015).
  29. R. Nedela and M. Škoviera, Regular embeddings of canonical double coverings of graphs, J. Combin. Theory Ser. B 67 (1996) 249–277.
    https://doi.org/10.1006/jctb.1996.0044
  30. S. Negami, Graphs which have no planar covering, Bull. Inst. Math. Acad. Sin. 16 (1988) 377–384.
  31. W.D. Neumann, On Leighton's graph covering theorem, Groups Geom. Dyn. 4 (2010) 863–872.
    https://doi.org/10.4171/ggd/111
  32. K. Reidemeister, Einführung in die kombinatorische Topologie, Monats. Math. 40 (1933) A9.
    https://doi.org/10.1007/BF01708901
  33. H. Sachs, Simultane Überlagerung gegebener Graphen, Publ. Math. Inst. Hung. Acad. Sci. Ser. A 9 (1965) 415–427.
Close