×

zbMATH — the first resource for mathematics

Induced hourglass and the equivalence between Hamiltonicity and supereulerianity in claw-free graphs. (English) Zbl 1298.05193
Summary: A graph \(H\) has the hourglass property if in every induced hourglass \(S\) (the unique simple graph with the degree sequence (4, 2, 2, 2, 2)), there are two non-adjacent vertices which have a common neighbor in \(H - V(S)\). Let \(G\) be a claw-free simple graph and \(k\) a positive integer. In this paper, we prove that if either \(G\) is hourglass-free or \(G\) has the hourglass property and \(\delta(G) \geq 4\), then \(G\) has a 2-factor with at most \(k\) components if and only if it has an even factor with at most \(k\) components. We provide some of its applications: combining the result (the case when \(k = 1\)) with [F. Jaeger, J. Graph Theory 3, 91–93 (1979; Zbl 0396.05034); Z.-H. Chen et al., J. Comb. Math. Comb. Comput. 59, 165–171 (2006; Zbl 1124.05054)], we obtain that every 4-edge-connected claw-free graph with the hourglass property is Hamiltonian and that every essentially 4-edge-connected claw-free hourglass-free graph of minimum degree at least three is Hamiltonian, thereby generalizing the main result in [T. Kaiser et al., J. Graph Theory 48, No. 4, 267–276 (2005; Zbl 1060.05064)] and the result in [H. J. Broersma et al., J. Graph Theory 37, No. 2, 125–136 (2001; Zbl 0984.05067)] respectively in which the conditions on the vertex-connectivity are replaced by the condition of (essential) 4-edge-connectivity. Combining our result with [P. A. Catlin and H.-J. Lai, Ars Comb. 30, 177–191 (1990; Zbl 0751.05064); H.-J. Lai et al., Ars Comb. 94, 191–199 (2010; Zbl 1240.05171); P. Paulraja, Ars Comb. 24, 57–65 (1987; Zbl 0662.05044)], we also obtain several other results on the existence of a Hamiltonian cycle in claw-free graphs in this paper.

MSC:
05C45 Eulerian and Hamiltonian graphs
05C38 Paths and cycles
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bondy, J. A.; Murty, U. S.R., Graph theory, (2008), Springer · Zbl 1134.05001
[2] Broersma, H. J.; Kriesell, M.; Ryjáček, Z., On factors of 4-connected claw-free graphs, J. Graph Theory, 37, 125-136, (2001) · Zbl 0984.05067
[3] Brousek, J.; Ryjáček, Z.; Schiermeyer, I., Forbidden subgraphs, stability and Hamiltonicity, Discrete Math., 197-198, 29-50, (1999) · Zbl 0927.05053
[4] Catlin, P. A.; Lai, H.-J., Eulerian subgraphs in graphs with short cycles, Ars Combin., 30, 177-191, (1990) · Zbl 0751.05064
[5] Chen, Z.-H.; Lai, H.-J.; Lou, W.; Shao, Y., Spanning Eulerian subgraphs in claw-free graphs, J. Combin. Math. Combin. Comput., 59, 165-171, (2006) · Zbl 1124.05054
[6] Gould, R.; Hynds, E., A note on cycles in 2-factor of line graphs, Bull. Inst. Combin. Appl., 26, 46-48, (1999) · Zbl 0922.05046
[7] Harary, F.; Nash-Williams, C. St. J.A., On eulerian and Hamiltonian graphs and line graphs, Canad. Math. Bull., 8, 701-710, (1965) · Zbl 0136.44704
[8] Jaeger, F., A note on Subeulerian graphs, J. Graph Theory, 3, 91-93, (1979)
[9] Kaiser, T.; Li, M. C.; Ryjáček, Z.; Xiong, L., Hourglasses and Hamilton cycles in 4-connected claw-free graphs, J. Graph Theory, 48, 267-276, (2005) · Zbl 1060.05064
[10] Lai, H.-J.; Shao, Y.; Li, M. C.; Xiong, L., Spanning Eulerian subgraphs in \(N^2\)-locally connected claw-free graphs, Ars Combin., 94, 191-199, (2010) · Zbl 1240.05171
[11] Lai, H.-J.; Shao, Y.; Yu, G.; Zhan, M., Hamiltonian connectedness in 3-connected line graphs, Discrete Appl. Math., 157, 982-990, (2009) · Zbl 1169.05344
[12] Matthews, M. M.; Sumner, D. P., Hamiltonian results in \(K_{1, 3}\)-free graphs, J. Graph Theory, 8, 139-146, (1984) · Zbl 0536.05047
[13] Paulraja, P., On graphs admitting spanning Eulerian subgraphs, Ars Combin., 24, 57-65, (1987) · Zbl 0662.05044
[14] Ryjáček, Z., On a closure concept in claw-free graphs, J. Combin. Theory Ser. B, 70, 2, 217-224, (1997) · Zbl 0872.05032
[15] Ryjáček, Z.; Saito, A.; Schelp, R. H., Closure, 2-factor and cycle coverings in claw-free graphs, J. Graph Theory, 32, 109-117, (1999) · Zbl 0932.05045
[16] Xiong, L., Closure operation for even factors on claw-free graphs, Discrete Math., 311, 1714-1723, (2011) · Zbl 1235.05116
[17] Xiong, L.; Liu, Z., Hamiltonian iterated line graphs, Discrete Math., 256, 407-422, (2002) · Zbl 1027.05055
[18] Xiong, L.; Liu, Z.; Yi, G., Characterization of the \(n\)-th super-Eulerian iterated line graph, J. Jiangxi Normal Univ., 24, 107-121, (2000), (in Chinese) · Zbl 1009.05122
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.