Article

Full entry | Fulltext not available (moving wall 24 months)
Keywords:
claw-free graph; 2-factor; closure; locally disconnected vertex; singular edge
Summary:
An edge of \$G\$ is singular if it does not lie on any triangle of \$G\$; otherwise, it is non-singular. A vertex \$u\$ of a graph \$G\$ is called locally connected if the induced subgraph \$G[N(u)]\$ by its neighborhood is connected; otherwise, it is called locally disconnected. In this paper, we prove that if a connected claw-free graph \$G\$ of order at least three satisfies the following two conditions: (i) for each locally disconnected vertex \$v\$ of degree at least \$3\$ in \$G,\$ there is a nonnegative integer \$s\$ such that \$v\$ lies on an induced cycle of length at least \$4\$ with at most \$s\$ non-singular edges and with at least \$s-5\$ locally connected vertices; (ii) for each locally disconnected vertex \$v\$ of degree \$2\$ in \$G,\$ there is a nonnegative integer \$s\$ such that \$v\$ lies on an induced cycle \$C\$ with at most \$s\$ non-singular edges and with at least \$s-3\$ locally connected vertices and such that \$G[V (C)\cap V_{2} (G)]\$ is a path or a cycle, then \$G\$ has a 2-factor, and it is the best possible in some sense. This result generalizes two known results in Faudree, Faudree and Ryjáček (2008) and in Ryjáček, Xiong and Yoshimoto (2010).
References:
[1] Bielak, H.: Sufficient condition for Hamiltonicity of \$N_{2}\$-locally connected claw-free graphs. Discrete Math. 213 (2000), 21-24. DOI 10.1016/S0012-365X(99)00163-6 | MR 1755406 | Zbl 0951.05069
[2] Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications. American Elsevier Publishing Co. New York (1976). MR 0411988
[3] Choudum, S. A., Paulraj, M. S.: Regular factors in \$K_{1, 3}\$-free graphs. J. Graph Theory 15 (1991), 259-265. DOI 10.1002/jgt.3190150304 | MR 1111989
[4] Egawa, Y., Ota, K.: Regular factors in \$K_{1, n}\$-free graphs. J. Graph Theory 15 (1991), 337-344. DOI 10.1002/jgt.3190150310 | MR 1111995
[5] Faudree, J. R., Faudree, R. J., Ryjáček, Z.: Forbidden subgraphs that imply 2-factors. Discrete Math. 308 (2008), 1571-1582. MR 2392597 | Zbl 1139.05049
[6] Gould, R. J., Hynds, E. A.: A note on cycles in 2-factors of line graphs. Bull. Inst. Comb. Appl. 26 (1999), 46-48. MR 1683819 | Zbl 0922.05046
[7] Li, M.: Hamiltonian cycles in \$N^{2}\$-locally connected claw-free graphs. Ars Comb. 62 (2002), 281-288. MR 1881966
[8] Oberly, D. J., Sumner, D. P.: Every connected, locally connected nontrivial graph with no induced claw is Hamiltonian. J. Graph Theory 3 (1979), 351-356. DOI 10.1002/jgt.3190030405 | MR 0549691
[9] Pfender, F.: Hamiltonicity and forbidden subgraphs in 4-connected graphs. J. Graph Theory 49 (2005), 262-272. DOI 10.1002/jgt.20080 | MR 2197229 | Zbl 1068.05042
[10] Ryjáček, Z.: On a closure concept in claw-free graphs. J. Comb. Theory, Ser. B 70 (1997), 217-224. DOI 10.1006/jctb.1996.1732 | MR 1459867
[11] Ryjáček, Z.: Hamiltonian circuits in \$N_{2}\$-locally connected \$K_{1,3}\$-free graphs. J. Graph Theory 14 (1990), 321-331. DOI 10.1002/jgt.3190140305 | MR 1060860
[12] Ryjáček, Z., Saito, A., Schelp, R. H.: Closure, 2-factors and cycle coverings in claw-free graphs. J. Graph Theory 32 (1999), 109-117. DOI 10.1002/(SICI)1097-0118(199910)32:2<109::AID-JGT1>3.0.CO;2-O | MR 1709653 | Zbl 0932.05045
[13] Ryjáček, Z., Xiong, L., Yoshimoto, K.: Closure concept for 2-factors in claw-free graphs. Discrete Math. 310 (2010), 1573-1579. DOI 10.1016/j.disc.2010.02.004 | MR 2601267 | Zbl 1225.05208
[14] Tian, R., Xiong, L.: Hamiltonian claw-free graphs with locally disconnected vertices. (to appear) in Discrete Math. DOI:10.1016/j.disc.2015.04.020. DOI 10.1016/j.disc.2015.04.020
[15] Yoshimoto, K.: On the number of components in 2-factors of claw-free graphs. Discrete Math. 307 (2007), 2808-2819. DOI 10.1016/j.disc.2006.11.022 | MR 2362964 | Zbl 1129.05037

Partner of