×

Hamiltonicity and restricted degree conditions on induced subgraphs in claw-free graphs. (English) Zbl 1455.05037

Summary: For a graph \(S\), a vertex with degree one in \(S\) is an end-vertex of \(S\) and an edge is a pendant edge if one of its ends is an end-vertex. A net \(N\) is a graph obtained from a \(K_3\) by adding a pendant edge at each vertex of the \(K_3\). A \(P_6\) is a path on 6 vertices. In this paper, we solve two conjectures and prove that for 2-connected claw-free graphs \(H\) and for a fixed graph \(S \in \{ N, P_6\}\), if the degree at each end-vertex of every induced copy of \(S\) is at least \((|V(H)| - 2) / 3\), then \(H\) is Hamiltonian. The case for \(S = N\) was conjectured by Broersma (1993); the case for \(S = P_6\) was conjectured by R. Čada et al. [Acta Math. Sin., Engl. Ser. 32, No. 7, 845–855 (2016; Zbl 1347.05037)].

MSC:

05C45 Eulerian and Hamiltonian graphs
05C07 Vertex degrees

Citations:

Zbl 1347.05037
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] C̃ada, R.; Li, B.-L.; Ning, B.; Zhang, S.-G., Induced subgraphs with large degrees at end-vertices for hamiltonicity of claw-free graphs, Acta Math. Sin. (Engl. Ser.), 32, 7, 845-855 (2016) · Zbl 1347.05037
[2] Bedrossian, P., Forbidden subgraph and minimum degree conditions for hamiltonicity (1991), Memphis State University: Memphis State University USA, (Ph.D. thesis)
[3] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), American Elsevier: American Elsevier New York · Zbl 1226.05083
[4] Broersma, H. J., Problem 2, (Workshop Cycles and Colourings (1993), Novy Smokovec: Novy Smokovec Slovakia), available on http://umv.science.upjs.sk/c&c/history/93problems.pdf
[5] Broersma, H. J.; Veldman, H. J., Restrictions on induced subgraphs ensuring Hamiltonicity or pancyclicity of K1, 3-free graphs, (Bodendiek, R., Contemporary Methods in Graph Theory (1990), BI-Wiss.- Verlag: BI-Wiss.- Verlag Mannheim-Wien-Zürich), 181-194 · Zbl 0723.05082
[6] Brousek, J.; Ryjáček, Z.; Favaron, O., Forbidden subgraphs, hamiltonicity and closure in claw-free graphs, Discrete Math., 196, 29-50 (1999) · Zbl 0927.05053
[7] Catlin, P. A., Supereulerian graphs, collapsible graphs, and four-cycles, Congr. Numer., 58, 233-246 (1987) · Zbl 0647.05037
[8] Catlin, P. A., A reduction method to find spanning eulerian subgraphs, J. Graph Theory, 12, 29-44 (1988) · Zbl 0659.05073
[9] Catlin, P. A.; Han, Z.; Lai, H.-J., Graphs without spanning closed trails, Discrete Math., 160, 81-91 (1996) · Zbl 0859.05060
[10] Chen, Z. H.; Lai, H.-J, Supereulerian graphs and Petersen graph II, Ars Combin., 48, 271-282 (1998) · Zbl 0962.05035
[11] Chen, Z.-H.; Lai, H.-J.; Xiong, L. M., Minimum degree conditions for the Hamiltonicity of 3-connected claw-free graphs, J. Combin. Theory Ser. B, 122, 167-186 (2017) · Zbl 1350.05086
[12] Faudree, R. J.; Gould, R. J., Characterizing forbidden pairs for hamiltonian properties, Discrete Math., 173, 45-60 (1997) · Zbl 0879.05050
[13] Faudree, R. J.; Gould, R. J.; Ryjáček, Z.; Schiermeyer, I., Forbidden subgraphs and pancyclicity, Congr. Numer., 109, 13-32 (1995) · Zbl 0904.05055
[14] Fujisawa, J.; Yamashita, T., Degree conditions on claws and modified claws for hamiltonicity of graphs, Discrete Math., 308, 1612-1619 (2008) · Zbl 1134.05019
[15] Harary, F.; St. J. A. Nash-Williams, C., On Eulerian and Hamiltonian graphs and line graphs, Canada Math. Bull., 8, 701-710 (1965) · Zbl 0136.44704
[16] Lai, H.-J., Contractions and hamiltonian line graphs, J. Graph Theory, 12, 11-15 (1988) · Zbl 0655.05046
[17] Lai, H.-J., Supereulerian graphs and excluded induced minors, Discrete Math., 146, 133-143 (1995) · Zbl 0844.05067
[18] Matthews, M.; Sumner, D., Longest paths and cycles in \(K_{1 , 3}\)-free graphs, J. Graph Theory, 9, 269-277 (1985) · Zbl 0591.05041
[19] Roussopoulos, N. D., A max \(\{ m , n \}\) algorithm for determining the graph \(H\) from its line graph \(G\), Inform. Process. Lett., 2, 108-112 (1973) · Zbl 0274.05116
[20] Ryjáček, Z., On a closure concept in claw-free graphs, J. Combin. Theory Ser. B, 70, 217-224 (1997) · Zbl 0872.05032
[21] Shao, Y., Claw-free graphs and line graphs (2005), West Virginia University, (Ph.D dissertation)
[22] Veldman, H. J., On dominating and spanning circuits in graphs, Discrete Math., 124, 229-239 (1994) · Zbl 0789.05061
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.