×

On Hamiltonicity of 3-connected claw-free graphs. (English) Zbl 1298.05192

Summary: H.-J. Lai et al. [J. Graph Theory 48, No. 2, 142–146 (2005; Zbl 1060.05061)] showed that every 3-connected \(N_2\)-locally connected claw-free graph is Hamiltonian. In this paper, we generalize this result and show that every 3-connected claw-free graph \(G\) such that every locally disconnected vertex lies on some induced cycle of length at least 4 with at most 4 edges contained in some triangle of \(G\) is Hamiltonian. It is best possible in some sense.

MSC:

05C45 Eulerian and Hamiltonian graphs
05C40 Connectivity

Citations:

Zbl 1060.05061
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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 · doi:10.1002/jgt.1008
[2] Brousek J., Ryjáček, Z., Schiermeyer I.: Forbidden subgraphs, stability and hamiltonicity. Discrete Math. 197(198), 29-50 (1999) · Zbl 0927.05053 · doi:10.1016/S0012-365X(98)00334-3
[3] Harary F., St C., Nash-Williams J.A.: On eulerian and hamiltonian graphs and line graphs. Can. Math. Bull. 8, 701-709 (1965) · Zbl 0136.44704 · doi:10.4153/CMB-1965-051-3
[4] Kaiser T., Li M., Ryjáček, Z., Xiong L.: Hourglasses and Hamilton cycle in 4-connected claw-free graphs. J. Graph Theory. 48, 267-276 (2005) · Zbl 1060.05064 · doi:10.1002/jgt.20056
[5] Lai H.-J.: Graph whose edges are in small cycles. Discrete Math. 94, 11-22 (1991) · Zbl 0761.05059 · doi:10.1016/0012-365X(91)90302-I
[6] Lai H.-J., Shao Y., Zhan M.: Hamiltonian N2-locally connected claw-free graphs. J. Graph Theory. 48, 142-146 (2005) · Zbl 1060.05061 · doi:10.1002/jgt.20046
[7] Li M., Guo C., Xiong L., Li D., Lai H.-J.: Quadrangularly connected claw-free graphs. Discrete Math. 307, 1205-1211 (2007) · Zbl 1118.05057 · doi:10.1016/j.disc.2006.07.034
[8] Matthews H.M., Sumner D.P.: Hamiltonian results in K1, 3-free graphs. J. Graph Theory. 8, 139-146 (1984) · Zbl 0536.05047 · doi:10.1002/jgt.3190080116
[9] 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 · doi:10.1002/jgt.3190030405
[10] Pfender F.: Hamiltonicity and forbidden subgraphs in 4-connected graphs. J. Graph Theory. 49, 262-272 (2005) · Zbl 1068.05042 · doi:10.1002/jgt.20080
[11] Ryjáček, Z.: Hamiltonian circuits in N2-locally connected K1, 3-free graphs. J. Graph Theory. 14, 321-331 (1990) · Zbl 0718.05036 · doi:10.1002/jgt.3190140305
[12] Ryjáček, Z.: On a closure concept in claw-free graphs. J. Combin. Theory Ser. B. 70, 217-224 (1997) · Zbl 0872.05032 · doi:10.1006/jctb.1996.1732
[13] Shao, Y.: Claw-free Graphs and Line Graphs, Ph.D. Dissertation, West Virginia University (2005) · Zbl 0929.05054
[14] Tian R., Xiong L.: On Hamiltonicity of 2-connected claw-free graphs. Appl. Math. J. Chin. Univ. 27(2), 234-242 (2012) · Zbl 1265.05322 · doi:10.1007/s11766-012-2835-6
[15] West, D.B.: Introduction to Graph Theory. 2nd edn. Prentice Hall, Upper Saddle River (2001) · Zbl 0984.05067
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.