Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
2-factor; claw-free graph; line graph; $N^{2}$-locally connected
2-factor; claw-free graph; line graph; $N^{2}$-locally connected
Summary:
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.
References:
[1] Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications. American Elsevier Publishing Co. New York (1976). MR 0411988
[2] 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
[3] 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
[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 1683819 | Zbl 0922.05046
[5] Li, G., Liu, Z.: On 2-factors in claw-free graphs. Syst. Sci. Math. Sci. 8 (1995), 369-372. MR 1374533 | Zbl 0851.05084
[6] 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
[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 10.1002/(SICI)1097-0118(199910)32:2<109::AID-JGT1>3.0.CO;2-O | MR 1709653 | Zbl 0932.05045
[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 10.1016/j.disc.2012.07.005 | MR 2957934 | Zbl 1251.05145
[9] 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
