No Detail Found!

What is and is not inside a Cayley graph?

Author(s)
Kolja Knauer Departament de Matema ́tiques i Informa ́tica, Universitat de Barcelona,Barcelona,Spain
A´ lvaro Soto Go´mez Departament de Matema ́tiques i Informa ́tica, Universitat de Barcelona,Barcelona,Spain
Abstract
In this paper, we show that there is a cubic graph of girth 5 that is not a subgraph of any minimal Cayley graph. On the other hand, we show that any generalized Petersen graph G(n, k) with gcd(n, k) = 1 is an induced subgraph of a minimal Cayley graph. These results give insights into two comments of L´aszl´o Babai [Automorphism groups, isomorphism, reconstruction, In: R. L. Graham, M. Gr¨otschel, L. Lov´asz (Eds.), Handbook of Combinatorics, Elsevier, Amsterdam, 1995, 1447–1540].
Publication Details
Page(s) 67-72
Published Journal: Discrete Mathematics Letters, Volume: 16, Issue: 0, Year: 2025

Request the full text from PASTIC

Keywords
minimal Cayley graph, cubic graph, generalized Petersen graph
References
Babai L.,Alavi D. R.,Lick D. R. .1978 .Chromatic number and subgraphs of Cayley graphs. Theory and Applications of Graphs, : 10-22.
Babai L. .1978 .mes combinatoires et the´orie des graphes. Colloq. Int. CNRS 260, : 13-15.
Babai L.,Graham L. .1995 .. Handbook of Combinatorics, : 1447-1540.
Babai L. .1985 .So´s, Sidon sets in groups and induced subgraphs of Cayley graphs. European J. Combin, 6 : 101-114.
Coolsaet K.,S. K. .2023 .0: a database of interesting graphs and more. Discrete Appl. Math, 325 : 97-107.
Coxeter H. S. M. .1950 .Self-dual configurations and regular graphs. Bull. Amer. Math. Soc, 56 : 413-455.
Davies J.,Hatzel M. .2024 .Counterexample to Babai's lonely colour conjecture. arXiv:2410.05199 [math.CO], : .
Farrokhi M.,Mohammadian A. .2016 .Groups whose all (minimal) Cayley graphs have a given forbidden structure. , : .
Frucht R.,Graver J. E.,M. E. Watkins, J. E. .1971 .The groups of the generalized Petersen graphs. Math. Proc. Cambridge Philos. Soc, 70 : 211-218.
I. ,Marco K.,Knauer K. .2022 .On sensitivity in bipartite Cayley graphs. J. Combin. Theory Ser. B, 154 : 211-238.
I. ,Marco K.,Knauer K. .2024 .Beyond symmetry in generalized Petersen graphs. J. Algebraic Combin, 59 : 331-357.
I. ,Marco K.,Knauer K. .2025 .Coloring minimal Cayley graphs. European J. Combin, 125 : 104108.
C. D. Godsil .1981 .Connectivity of minimal Cayley graphs. , 37 : 473-476.
C. D. Godsil .1987 .Embedding graphs in Cayley graphs. Graphs Combin, 3 : 39-43.
Hassani A.,Iranmanesh M. A. .1996 .On Cayley graphs related to finite groups with minimal generator set. In: Proc. 27th Annual Iranian Mathematics Conference, : 107-111.
Knauer U.,Knauer K. .2019 .. , : .
Li C. H.,Zhou S. .2001 .On isomorphisms of minimal Cayley graphs and digraphs. Graphs Combin, 17 : 307-314.
M. Lovrecic Sarazˇin .1997 .A note on the generalized Petersen graphs that are also Cayley graphs. J. Combin. Theory Ser. B, 69 : 226-229.
Sˇ . Miklavic P. .2020 .Sˇ parl, On minimal distance-regular Cayley graphs of generalized dihedral groups. Electron. J. Combin, 27 : 33.
Nedela R.,M. R. .1995 .Sˇkoviera, Which generalized Petersen graphs are Cayley graphs?. J. Graph Theory, 19 : 1-11.
I. Pak ,R. .2009 .Radoicˇic´, Hamiltonian paths in Cayley graphs. , 309 : 5501-5508.
Potocnik P.,Evans R. .2025 .Datasets of highly symmetric objects. Accessed: April, 17 : .
Slupik A. J.,V. I. Sushchansky A. J. .2009 .Minimal generating sets and Cayley graphs of Sylow p-subgroups of finite symmetric groups. Algebra Discrete Math, : 167-184.
´ . Soto A . .Go´mez, Code for “What is and is not inside a Cayley graph?”. , : .
Spencer J. .1983 .What's not inside a Cayley graph. Combinatorica, 3 : 239-241.
Steimle A. .2009 .The isomorphism classes of the generalized Petersen graphs. , 309 : 231-237.
Watkins M. E. .1969 .A theorem on Tait colorings with an application to the generalized Petersen graphs. J. Combin. Theory, 6 : 152-164.
White A. T. .2001 .. Graphs of Groups on Surfaces: Interactions and Models, : .
0

Citations

0

Downloads

30

Views