×

On a closure concept in claw-free graphs. (English) Zbl 0872.05032

If \(G\) is a claw-free graph, then there is a graph \(cl(G)\) such that (i) \(G\) is a spanning subgraph of \(cl(G)\), (ii) \(cl(G)\) is a line graph of a triangle-free graph, and (iii) the length of a longest cycle in \(G\) and in \(cl(G)\) is the same. A sufficient condition for hamiltonicity in claw-free graphs, the equivalence of some conjectures on hamiltonicity in 2-tough graphs and the hamiltonicity of 7-connected claw-free graphs are obtained as corollaries.

MSC:

05C45 Eulerian and Hamiltonian graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), Macmillan: Macmillan London · Zbl 1134.05001
[2] Chvátal, V., Tough graphs and hamiltonian circuits, Discrete Math., 5, 215-228 (1973) · Zbl 0256.05122
[3] Enomoto, H.; Jackson, B.; Katerinis, P.; Saito, A., Toughness and the existence of k-factors, J. Graph Theory, 9, 87-95 (1985) · Zbl 0598.05054
[4] R. Faudree, Z. Ryjáček, I. Schiermeyer, Local connectivity and cycle extension in claw-free graphs, Ars Combinatoria; R. Faudree, Z. Ryjáček, I. Schiermeyer, Local connectivity and cycle extension in claw-free graphs, Ars Combinatoria
[5] B. Jackson, 1989, Hamilton cycles in 7-connected line graphs, preprint; B. Jackson, 1989, Hamilton cycles in 7-connected line graphs, preprint
[6] Matthews, M. M.; Sumner, D. P., Hamiltonian results in \(K_{1, 3}\), J. Graph Theory, 8, 139-146 (1984) · Zbl 0536.05047
[7] Oberly, D. J.; Sumner, D. P., Every connected, locally connected nontrivial graph with no induced claw is hamiltonian, J. Graph Theory, 3, 351-356 (1979) · Zbl 0424.05036
[8] Ryjáček, Z., Hamiltonian circuits in \(N_2K_{1, 3}\), J. Graph Theory, 14, 321-331 (1990)
[9] Thomassen, C., Reflections on graph theory, J. Graph Theory, 10, 309-324 (1986) · Zbl 0614.05050
[10] Zhan, S., On hamiltonian line graphs and connectivity, Discrete Math., 89, 89-95 (1991) · Zbl 0727.05037
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.