Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
claw-free graph; 2-factor; closure; locally disconnected vertex; singular edge
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
Search
Partner of
