×

Global insertion and Hamiltonicity in DCT-graphs. (English) Zbl 0958.05084

Summary: In a new class of graphs strictly containing the class of almost claw-free graphs, the class of quasi claw-free graphs and thus the class of claw-free graphs, we show that if the graph \(G\) is 2-connected of order \(n\) and if the degree sum of any three independent vertices is at least \(n-2\), then \(G\) is Hamiltonian. This problem was posed for almost claw-free graphs by Broersma et al. (1996) and was settled by Li and Tian when \(n\geq 79\) for another class containing the almost claw-free graphs. We also consider properties of matchings and toughness in this new class. In the main proof, we introduce a technique of global insertion which is a more powerful tool than the usual insertion.

MSC:

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

References:

[1] Ainouche, A., An improvement of Fraisse’s sufficient condition for hamiltonian graphs, J. Graph Theory, 16, 6, 529-543 (1992) · Zbl 0770.05070
[2] Ainouche, A., Quasi claw-free graphs, Discrete Math., 179, 13-26 (1998) · Zbl 0888.05038
[3] Ainouche, A.; Broersma, H. J.; Veldman, H. J., Remarks on hamiltonian properties of claw-free graphs, Ars Combin. C, 29, 110-121 (1990) · Zbl 0715.05048
[4] Broersma, H. J.; Ryjáček, Z.; Schiermeyer, I., Toughness and hamiltonicity in almost claw-free graphs, J. Graph Theory, 21, 4, 431-439 (1996) · Zbl 0847.05069
[5] O. Favaron, E. Flandrin, Z. Ryjáček, Factor-criticality and matching extension in DCT-graphs, Discussiones Mathematicae-Graph Theory, to appear.; O. Favaron, E. Flandrin, Z. Ryjáček, Factor-criticality and matching extension in DCT-graphs, Discussiones Mathematicae-Graph Theory, to appear.
[6] Flandrin, E.; Jung, H. A.; Li, H., Hamiltonism, degree sums and neighborhood intersections, Discrete Math., 90, 41-52 (1991) · Zbl 0746.05038
[7] Li, H.; Tian, F., Degree sums, claws and hamiltonicity, (RR L.R.I No. 886 (1/1994), Université de Paris Sud: Université de Paris Sud Orsay, France)
[8] Matthews, M. M.; Sumner, D. P., Longest paths and cycles in \(K_{1,3}\)-free graphs, J. Graph Theory, 9, 269-277 (1985) · Zbl 0591.05041
[9] Ryjáček, Z., Almost claw-free graphs, J. Graph Theory, 18, 5, 469-477 (1994) · Zbl 0808.05067
[10] Sumner, D. P., Graphs with 1-factors, (Proc. Amer. Math. Soc., 42 (1974)), 8-13 · Zbl 0293.05157
[11] Sumner, D. P., 1-factors and antifactor sets, J. London Math. Soc., 2, 13, 351-359 (1976) · Zbl 0338.05118
[12] Zhang, C. Q., Hamilton cycles in claw-free graphs, J. Graph Theory, 12, 2, 209-216 (1988) · Zbl 0642.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.