On the Erdős-Gyárfás conjecture for some Cayley graphs. (English) Zbl 1474.05221

Ghasemi, Mohsen; Varmazyar, Rezvan

Mat. Vesn. 73, No. 1, 37-42 (2021).

Summary: In 1995, Paul Erdős and András Gyárfás [P. Erdős, Discrete Math. 165–166, 227–231 (1997; Zbl 0872.05020)] conjectured that for every graph \(X\) of minimum degree at least \(3\), there exists a non-negative integer \(m\) such that \(X\) contains a simple cycle of length \(2^m\). In this paper, we prove that the conjecture holds for Cayley graphs of order \(2p^2\) and \(4p\).

MSC:

05C38	Paths and cycles
05C25	Graphs and abstract algebra (groups, rings, fields, etc.)
20B25	Finite automorphism groups of algebraic, geometric, or combinatorial structures

Keywords:

Erdős-Gyárfás conjecture; Cayley graphs; cycles of graphs

Citations:

Zbl 0872.05020

References:

[1]	J.A. Bondy,Extremal problems of Paul Erd˝os on circuits in graphs, in: Paul Erd˝os and his Mathematics, II, Bolyai Soc. Math. Stud., 11, Janos Bolyai Math. Soc., Budapest (2002), 135-156. · Zbl 1051.05051
[2]	D. Daniel, S.E. Shauger,A result on the Erd˝os-Gyarfas conjecture in planer graphs, In: Proceedings of the Thirty-Second Southeastern International Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, LA, 2001),153, 129-139. · Zbl 0997.05053
[3]	P. Erd˝os,Some old and new problems in various branches of combinatorics, Discrete Math., 165/166(1997), 227-231. · Zbl 0872.05020
[4]	M.H Ghaffari, Z. Mostaghim,Erd˝os-Gyarfas conjecture for some families of Cayley graphs, Aequat. Math.,92(2017), 1-6. · Zbl 1489.05080
[5]	C.C. Heckman, R. Krakovski,Erd˝os-Gyarfas conjecture for cubic planar graphs, Electron. J. Comb.,20(2)(2013), 7-43. · Zbl 1267.05152
[6]	K. Markstr¨om,Extremal graphs for some problems on cycles in graphs, In: Proceedings of the Thirty-Fifth Southeastern International Conference on Combinatorics, Graph Theory and Computing,171(2004), 179-192. · Zbl 1063.05073
[7]	P.S. Nowbandegani, H. Esfandiari, M.H. Shirdareh Haghighi, B. Khodakhast,Note on the Erd˝os-Gyarfas conjecture in claw-free graphs, Discuss. Math. Graph Theory.,34(2014), 635- 640. · Zbl 1295.05135
[8]	S.E. Shauger,Results on the Erd˝os-Gyarfas conjecture inK1,m-free graphs, In: Proceedings of the Twenty-Ninth Southeastern International Conference on Combinatorics, Graph Theory and Computing(Boca Raton, FL, 1998),134(1998), 61-65. · Zbl 0952.05038