×

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

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

Citations:

Zbl 0872.05020
PDF BibTeX XML Cite
Full Text: Link Link

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.
[4] M.H Ghaffari, Z. Mostaghim,Erd˝os-Gyarfas conjecture for some families of Cayley graphs, Aequat. Math.,92(2017), 1-6.
[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.
[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.