Graph covers and generalized snarks

EUROCOMB’23

Jan Kratochvil Roman Nedela

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-094

PDF
Abstract
The notion of graph cover, also known as locally bijective homomorphism, is a discretization of covering spaces known from general topology. It is a pair of incidence-preserving vertex- and edge-mappings between two graphs, the edge-component being bijective on the edge-neighborhoods of every vertex and its image. In line with the current trends in topological graph theory and its applications in mathematical physics, graphs are considered in the most relaxed form and as such they may contain multiple edges, loops and semi-edges. Nevertheless, simple graphs (binary structures without multiple edges, loops, or semi-edges) play an important role. The Strong Dichotomy Conjecture of Bok et al. [2022] states that for every fixed graph $H$, deciding if an input graph covers $H$ is either polynomial time solvable for arbitrary input graphs, or NP-complete for simple ones. These authors introduced the following quasi-order on the class of connected graphs: A connected graph $A$ is called stronger than a connected graph $B$ if every simple graph that covers $A$ also covers $B$. Witnesses of $A$ not being stronger than $B$ are generalized snarks in the sense that they are simple graphs that cover $A$ but do not cover $B$. Bok et al. conjectured that if $A$ has no semi-edges, then $A$ is stronger than $B$ if and only if $A$ covers $B$. We prove this conjecture for cubic one-vertex graphs, and we also justify it for all cubic graphs $A$ with at most 4 vertices.

Pages:
681–687
References

James Abello, Michael R. Fellows, and John C. Stillwell. On the complexity and combinatorics of covering finite complexes. Australian Journal of Combinatorics, 4:103-112, 1991.

Norman Biggs. Algebraic graph theory. Cambridge University Press, 1974.
https://doi.org/10.1017/CBO9780511608704

Hans L. Bodlaender. The classification of coverings of processor networks. Journal of Parallel Distributed Computing, 6:166-182, 1989.
https://doi.org/10.1016/0743-7315(89)90048-8

Jan Bok, Jiří Fiala, Petr Hliněný, Nikola Jedličková, and Jan Kratochvíl. Computational complexity of covering multigraphs with semi-edges: Small cases. In Filippo Bonchi and Simon J. Puglisi, editors, 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, August 23-27, 2021, Tallinn, Estonia, volume 202 of LIPIcs, pages 21:1-21:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.

Jan Bok, Jiří Fiala, Nikola Jedličková, Jan Kratochvíl, and Michaela Seifrtová. Computational complexity of covering disconnected multigraphs. In Evripidis Bampis and Aris Pagourtzis, editors, Fundamentals of Computation Theory, volume 12867 of Lecture Notes in Computer Science, pages 85-99. Springer, 2021.
https://doi.org/10.1007/978-3-030-86593-1_6

Jan Bok, Jiří Fiala, Nikola Jedličková, Jan Kratochvíl, and Pawel Rzazewski. List covering of regular multigraphs. In Cristina Bazgan and Henning Fernau, editors, Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Trier, Germany, June 7-9, 2022, Proceedings, volume 13270 of Lecture Notes in Computer Science, pages 228-242. Springer, 2022.
https://doi.org/10.1007/978-3-031-06678-8_17

Miquel Angel Fiol, Giuseppe Mazzuoccolo, and Eckhard Steffen. Measures of edgeuncolorability of cubic graphs. Electronic journal of combinatorics, 25(4):# P4.54, 2018.
https://doi.org/10.37236/6848

Jonathan L. Gross. Voltage graphs. Discrete mathematics, 9(3):239-246, 1974.
https://doi.org/10.1016/0012-365X(74)90006-5

Jonathan L. Gross and Seth R. Alpert. The topological theory of current graphs. Journal of Combinatorial Theory, Series B, 17(3):218-233, 1974.
https://doi.org/10.1016/0095-8956(74)90028-8

Jonathan L. Gross and Thomas W. Tucker. Topological graph theory. Courier Corporation, 2001.

Robert Jajcay and Jozef Širáň. Small vertex-transitive graphs of given degree and girth. Ars Mathematica Contemporanea, 4(2):375-384, 2011.
https://doi.org/10.26493/1855-3974.124.06d

Jan Kratochvíl. Towards strong dichotomy of graph covers. In GROW 2022 - Book of Open Problems, page 10, 2022.

Aleksander Malnič, Roman Nedela, and Martin Škoviera. Lifting graph automorphisms by voltage assignments. European Journal of Combinatorics, 21(7):927-947, 2000.
https://doi.org/10.1006/eujc.2000.0390

Jan Mazák, J. Rajník, and Martin Škoviera. Morphology of small snarks. Electronic J. Combin., 29(4), 2022.
https://doi.org/10.37236/10917

Mirka Miller and Jozef Širáň. Moore graphs and beyond: A survey of the degree/diameter problem. The electronic journal of combinatorics, 20(2):# DS14v2, 2013.
https://doi.org/10.37236/35

Roman Nedela and Martin Škoviera. Cayley snarks and almost simple groups. Combinatorica, 21:583-590, 2001.
https://doi.org/10.1007/s004930100014

Gerhard Ringel. Map color theorem, volume 209. Springer Science & Business Media, 2012.

Gerhard Ringel and John W. T. Youngs. Solution of the Heawood map-coloring problem. Proceedings of the National Academy of Sciences, 60(2):438-445, 1968.
https://doi.org/10.1073/pnas.60.2.438

John J. Watkins. Snarks. Annals of the New York Academy of Sciences, 576(1):606-622, 1989.
https://doi.org/10.1111/j.1749-6632.1989.tb16441.x

Arthur T. White. Graphs, groups and surfaces. Elsevier, 1985.

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Jan Kratochvil, Roman Nedela

PDF