| Title:
|
Two operations on a graph preserving the (non)existence of 2-factors in its line graph (English) |
| Author:
|
An, Mingqiang |
| Author:
|
Lai, Hong-Jian |
| Author:
|
Li, Hao |
| Author:
|
Su, Guifu |
| Author:
|
Tian, Runli |
| Author:
|
Xiong, Liming |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
64 |
| Issue:
|
4 |
| Year:
|
2014 |
| Pages:
|
1035-1044 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
2-factor |
| Keyword:
|
claw-free graph |
| Keyword:
|
line graph |
| Keyword:
|
$N^{2}$-locally connected |
| MSC:
|
05C35 |
| MSC:
|
05C38 |
| MSC:
|
05C45 |
| idZBL:
|
Zbl 06433712 |
| idMR:
|
MR3304796 |
| DOI:
|
10.1007/s10587-014-0151-4 |
| . |
| Date available:
|
2015-02-09T17:38:30Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/144159 |
| . |
| Reference:
|
[1] Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications.American Elsevier Publishing Co. New York (1976). MR 0411988 |
| Reference:
|
[2] Choudum, S. A., Paulraj, M. S.: Regular factors in $K_{1, 3}$-free graphs.J. Graph Theory 15 (1991), 259-265. MR 1111989, 10.1002/jgt.3190150304 |
| Reference:
|
[3] Egawa, Y., Ota, K.: Regular factors in $K_{1, n}$-free graphs.J. Graph Theory 15 (1991), 337-344. MR 1111995, 10.1002/jgt.3190150310 |
| Reference:
|
[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. Zbl 0922.05046, MR 1683819 |
| Reference:
|
[5] Li, G., Liu, Z.: On 2-factors in claw-free graphs.Syst. Sci. Math. Sci. 8 (1995), 369-372. Zbl 0851.05084, MR 1374533 |
| Reference:
|
[6] Ryjáček, Z.: On a closure concept in claw-free graphs.J. Comb. Theory, Ser. B 70 (1997), 217-224. MR 1459867, 10.1006/jctb.1996.1732 |
| Reference:
|
[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. Zbl 0932.05045, MR 1709653, 10.1002/(SICI)1097-0118(199910)32:2<109::AID-JGT1>3.0.CO;2-O |
| Reference:
|
[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. Zbl 1251.05145, MR 2957934, 10.1016/j.disc.2012.07.005 |
| Reference:
|
[9] Yoshimoto, K.: On the number of components in 2-factors of claw-free graphs.Discrete Math. 307 (2007), 2808-2819. Zbl 1129.05037, MR 2362964, 10.1016/j.disc.2006.11.022 |
| . |
