Geodesic
2-factors in claw-free graphs with locally disconnected vertices
Czechoslovak Mathematical Journal, Tome 65 (2015) no. 2, pp. 317-330 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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).
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).
DOI : 10.1007/s10587-015-0177-2
Classification : 05C35, 05C38, 05C45
Keywords: claw-free graph; 2-factor; closure; locally disconnected vertex; singular edge 
@article{10_1007_s10587_015_0177_2,
     author = {An, Mingqiang and Xiong, Liming and Tian, Runli},
     title = {2-factors in claw-free graphs with locally disconnected vertices},
     journal = {Czechoslovak Mathematical Journal},
     pages = {317--330},
     year = {2015},
     volume = {65},
     number = {2},
     doi = {10.1007/s10587-015-0177-2},
     mrnumber = {3360428},
     zbl = {06486948},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0177-2/}
}
TY  - JOUR
AU  - An, Mingqiang
AU  - Xiong, Liming
AU  - Tian, Runli
TI  - 2-factors in claw-free graphs with locally disconnected vertices
JO  - Czechoslovak Mathematical Journal
PY  - 2015
SP  - 317
EP  - 330
VL  - 65
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0177-2/
DO  - 10.1007/s10587-015-0177-2
LA  - en
ID  - 10_1007_s10587_015_0177_2
ER  - 
%0 Journal Article
%A An, Mingqiang
%A Xiong, Liming
%A Tian, Runli
%T 2-factors in claw-free graphs with locally disconnected vertices
%J Czechoslovak Mathematical Journal
%D 2015
%P 317-330
%V 65
%N 2
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0177-2/
%R 10.1007/s10587-015-0177-2
%G en
%F 10_1007_s10587_015_0177_2
An, Mingqiang; Xiong, Liming; Tian, Runli. 2-factors in claw-free graphs with locally disconnected vertices. Czechoslovak Mathematical Journal, Tome 65 (2015) no. 2, pp. 317-330. doi: 10.1007/s10587-015-0177-2

[1] Bielak, H.: Sufficient condition for Hamiltonicity of $N_{2}$-locally connected claw-free graphs. Discrete Math. 213 (2000), 21-24. | DOI | MR | Zbl

[2] Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications. American Elsevier Publishing Co. New York (1976). | MR

[3] Choudum, S. A., Paulraj, M. S.: Regular factors in $K_{1, 3}$-free graphs. J. Graph Theory 15 (1991), 259-265. | DOI | MR

[4] Egawa, Y., Ota, K.: Regular factors in $K_{1, n}$-free graphs. J. Graph Theory 15 (1991), 337-344. | DOI | MR

[5] Faudree, J. R., Faudree, R. J., Ryjáček, Z.: Forbidden subgraphs that imply 2-factors. Discrete Math. 308 (2008), 1571-1582. | MR | Zbl

[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 | Zbl

[7] Li, M.: Hamiltonian cycles in $N^{2}$-locally connected claw-free graphs. Ars Comb. 62 (2002), 281-288. | MR

[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 | MR

[9] Pfender, F.: Hamiltonicity and forbidden subgraphs in 4-connected graphs. J. Graph Theory 49 (2005), 262-272. | DOI | MR | Zbl

[10] Ryjáček, Z.: On a closure concept in claw-free graphs. J. Comb. Theory, Ser. B 70 (1997), 217-224. | DOI | MR

[11] Ryjáček, Z.: Hamiltonian circuits in $N_{2}$-locally connected $K_{1,3}$-free graphs. J. Graph Theory 14 (1990), 321-331. | DOI | MR

[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 | MR | Zbl

[13] Ryjáček, Z., Xiong, L., Yoshimoto, K.: Closure concept for 2-factors in claw-free graphs. Discrete Math. 310 (2010), 1573-1579. | DOI | MR | Zbl

[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

[15] Yoshimoto, K.: On the number of components in 2-factors of claw-free graphs. Discrete Math. 307 (2007), 2808-2819. | DOI | MR | Zbl

Cité par Sources :