×

Cycles with a chord in dense graphs. (English) Zbl 1388.05104

Summary: A cycle of order \(k\) is called a \(k\)-cycle. A non-induced cycle is called a chorded cycle. Let \(n\) be an integer with \(n \geq 4\). Then a graph \(G\) of order \(n\) is chorded pancyclic if \(G\) contains a chorded \(k\)-cycle for every integer \(k\) with \(4 \leq k \leq n\). M. Cream et al. [Australas. J. Comb. 67, 463–469 (2017; Zbl 1375.05073)] proved that a graph of order \(n\) satisfying \(\deg_G u + \deg_G v \geq n\) for every pair of nonadjacent vertices \(u\), \(v\) in \(G\) is chorded pancyclic unless \(G\) is either \(K_{\frac{n}{2}, \frac{n}{2}}\) or \(K_3 \square K_2\), the Cartesian product of \(K_3\) and \(K_2\). They also conjectured that if \(G\) is Hamiltonian, we can replace the degree sum condition with the weaker density condition \(| E(G) | \geq \frac{1}{4} n^2\) and still guarantee the same conclusion. In this paper, we prove this conjecture by showing that if a graph \(G\) of order \(n\) with \(| E(G) | \geq \frac{1}{4} n^2\) contains a \(k\)-cycle, then \(G\) contains a chorded \(k\)-cycle, unless \(k = 4\) and \(G\) is either \(K_{\frac{n}{2}, \frac{n}{2}}\) or \(K_3 \square K_2\), Then observing that \(K_{\frac{n}{2}, \frac{n}{2}}\) and \(K_3 \square K_2\) are exceptions only for \(k = 4\), we further relax the density condition for sufficiently large \(k\).

MSC:

05C42 Density (toughness, etc.)
05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs

Citations:

Zbl 1375.05073
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alspach, B. R.; Godsil, C. D., Cycles in graphs, Ann. Discrete Math., 27, 461-468 (1985) · Zbl 0563.00004
[2] Bollobás, B.; Thomason, A., Weakly pancyclic graphs, J. Combin. Theory Ser. B, 77, 121-137 (1999) · Zbl 1023.05083
[3] Bondy, J. A., Pancyclic graphs I, J. Combin. Theory Ser. B, 11, 80-84 (1971) · Zbl 0183.52301
[4] Brandt, S., A sufficient condition for all short cycles, Discrete Appl. Math., 79, 63-66 (1997) · Zbl 0882.05081
[5] Chartrand, G.; Lesniak, L.; Zhang, P., Graphs & Digraphs (2011), Chapman and Hall/CRC: Chapman and Hall/CRC Boca Raton, Florida, USA · Zbl 1211.05001
[6] Cream, M.; Gould, R. J.; Hirohata, K., A note on extending Bondy’s meta-conjecture, Australas. J. Combin., 67, 463-469 (2017) · Zbl 1375.05073
[7] Faudree, R. J.; Schelp, R. H.; Saito, A.; Schiermeyer, I., Degree conditions for Hamiltonicity: counting the number of missing edges, Discrete Math., 307, 873-877 (2007) · Zbl 1122.05055
[8] Häggkvist, R.; Faudree, R. J.; Schelp, R. H., Pancyclic graphs - connected Ramsey number, Ars Combin., 26, 229-232 (1988)
[9] Thomassen, C., Configurations in graphs of large minimum degree, connectivity, or chromatic number, Combinatorial Mathematics: Proceedings of the Third International Conference, New York, 1985. Combinatorial Mathematics: Proceedings of the Third International Conference, New York, 1985, Ann. New York Acad. Sci., New York, 555, 402-412 (1989) · Zbl 0709.05030
[10] Thomassen, C., Independent dominating sets and a second Hamiltonian cycle in regular graphs, J. Combin. Theory Ser. B, 72, 104-109 (1998) · Zbl 0895.05038
[11] Thomassen, C., Chords in longest cycles, J. Combin. Theory Ser. B, 129, 148-157 (2018) · Zbl 1379.05032
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.