Geodesic
Two operations on a graph preserving the (non)existence of 2-factors in its line graph
Czechoslovak Mathematical Journal, Tome 64 (2014) no. 4, pp. 1035-1044 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Let $G=(V(G),E(G))$ be a graph. Gould and Hynds (1999) showed a well-known characterization of $G$ by its line graph $L(G)$ that has a 2-factor. In this paper, by defining two operations, we present a characterization for a graph $G$ to have a 2-factor in its line graph $L(G).$ A graph $G$ is called $N^{2}$-locally connected if for every vertex $x\in V(G),$ $G[\{y\in V(G)\; 1\leq {\rm dist}_{G}(x,y)\leq 2\}]$ is connected. By applying the new characterization, we prove that every claw-free graph in which every edge lies on a cycle of length at most five and in which every vertex of degree two that lies on a triangle has two $N^{2}$-locally connected adjacent neighbors, has a $2$-factor. This result generalizes the previous results in papers: Li, Liu (1995) and Tian, Xiong, Niu (2012), and is the best possible.
Let $G=(V(G),E(G))$ be a graph. Gould and Hynds (1999) showed a well-known characterization of $G$ by its line graph $L(G)$ that has a 2-factor. In this paper, by defining two operations, we present a characterization for a graph $G$ to have a 2-factor in its line graph $L(G).$ A graph $G$ is called $N^{2}$-locally connected if for every vertex $x\in V(G),$ $G[\{y\in V(G)\; 1\leq {\rm dist}_{G}(x,y)\leq 2\}]$ is connected. By applying the new characterization, we prove that every claw-free graph in which every edge lies on a cycle of length at most five and in which every vertex of degree two that lies on a triangle has two $N^{2}$-locally connected adjacent neighbors, has a $2$-factor. This result generalizes the previous results in papers: Li, Liu (1995) and Tian, Xiong, Niu (2012), and is the best possible.
DOI : 10.1007/s10587-014-0151-4
Classification : 05C35, 05C38, 05C45
Keywords: 2-factor; claw-free graph; line graph; $N^{2}$-locally connected 
@article{10_1007_s10587_014_0151_4,
     author = {An, Mingqiang and Lai, Hong-Jian and Li, Hao and Su, Guifu and Tian, Runli and Xiong, Liming},
     title = {Two operations on a graph preserving the (non)existence of 2-factors in its line graph},
     journal = {Czechoslovak Mathematical Journal},
     pages = {1035--1044},
     year = {2014},
     volume = {64},
     number = {4},
     doi = {10.1007/s10587-014-0151-4},
     mrnumber = {3304796},
     zbl = {06433712},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-014-0151-4/}
}
TY  - JOUR
AU  - An, Mingqiang
AU  - Lai, Hong-Jian
AU  - Li, Hao
AU  - Su, Guifu
AU  - Tian, Runli
AU  - Xiong, Liming
TI  - Two operations on a graph preserving the (non)existence of 2-factors in its line graph
JO  - Czechoslovak Mathematical Journal
PY  - 2014
SP  - 1035
EP  - 1044
VL  - 64
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-014-0151-4/
DO  - 10.1007/s10587-014-0151-4
LA  - en
ID  - 10_1007_s10587_014_0151_4
ER  - 
%0 Journal Article
%A An, Mingqiang
%A Lai, Hong-Jian
%A Li, Hao
%A Su, Guifu
%A Tian, Runli
%A Xiong, Liming
%T Two operations on a graph preserving the (non)existence of 2-factors in its line graph
%J Czechoslovak Mathematical Journal
%D 2014
%P 1035-1044
%V 64
%N 4
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-014-0151-4/
%R 10.1007/s10587-014-0151-4
%G en
%F 10_1007_s10587_014_0151_4
An, Mingqiang; Lai, Hong-Jian; Li, Hao; Su, Guifu; Tian, Runli; Xiong, Liming. Two operations on a graph preserving the (non)existence of 2-factors in its line graph. Czechoslovak Mathematical Journal, Tome 64 (2014) no. 4, pp. 1035-1044. doi: 10.1007/s10587-014-0151-4

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

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

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

[4] 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

[5] Li, G., Liu, Z.: On 2-factors in claw-free graphs. Syst. Sci. Math. Sci. 8 (1995), 369-372. | MR | Zbl

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

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

[8] Tian, R., Xiong, L., Niu, Z.: On 2-factors in claw-free graphs whose edges are in small cycles. Discrete Math. 312 (2012), 3140-3145. | DOI | MR | Zbl

[9] 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 :