| Title:
|
2-factors in claw-free graphs with locally disconnected vertices (English) |
| Author:
|
An, Mingqiang |
| Author:
|
Xiong, Liming |
| Author:
|
Tian, Runli |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
65 |
| Issue:
|
2 |
| Year:
|
2015 |
| Pages:
|
317-330 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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). (English) |
| Keyword:
|
claw-free graph |
| Keyword:
|
2-factor |
| Keyword:
|
closure |
| Keyword:
|
locally disconnected vertex |
| Keyword:
|
singular edge |
| MSC:
|
05C35 |
| MSC:
|
05C38 |
| MSC:
|
05C45 |
| idZBL:
|
Zbl 06486948 |
| idMR:
|
MR3360428 |
| DOI:
|
10.1007/s10587-015-0177-2 |
| . |
| Date available:
|
2015-06-16T17:33:23Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/144271 |
| . |
| Reference:
|
[1] Bielak, H.: Sufficient condition for Hamiltonicity of $N_{2}$-locally connected claw-free graphs.Discrete Math. 213 (2000), 21-24. Zbl 0951.05069, MR 1755406, 10.1016/S0012-365X(99)00163-6 |
| Reference:
|
[2] Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications.American Elsevier Publishing Co. New York (1976). MR 0411988 |
| Reference:
|
[3] 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:
|
[4] 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:
|
[5] Faudree, J. R., Faudree, R. J., Ryjáček, Z.: Forbidden subgraphs that imply 2-factors.Discrete Math. 308 (2008), 1571-1582. Zbl 1139.05049, MR 2392597 |
| Reference:
|
[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. Zbl 0922.05046, MR 1683819 |
| Reference:
|
[7] Li, M.: Hamiltonian cycles in $N^{2}$-locally connected claw-free graphs.Ars Comb. 62 (2002), 281-288. MR 1881966 |
| Reference:
|
[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. MR 0549691, 10.1002/jgt.3190030405 |
| Reference:
|
[9] Pfender, F.: Hamiltonicity and forbidden subgraphs in 4-connected graphs.J. Graph Theory 49 (2005), 262-272. Zbl 1068.05042, MR 2197229, 10.1002/jgt.20080 |
| Reference:
|
[10] 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:
|
[11] Ryjáček, Z.: Hamiltonian circuits in $N_{2}$-locally connected $K_{1,3}$-free graphs.J. Graph Theory 14 (1990), 321-331. MR 1060860, 10.1002/jgt.3190140305 |
| Reference:
|
[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. Zbl 0932.05045, MR 1709653, 10.1002/(SICI)1097-0118(199910)32:2<109::AID-JGT1>3.0.CO;2-O |
| Reference:
|
[13] Ryjáček, Z., Xiong, L., Yoshimoto, K.: Closure concept for 2-factors in claw-free graphs.Discrete Math. 310 (2010), 1573-1579. Zbl 1225.05208, MR 2601267, 10.1016/j.disc.2010.02.004 |
| Reference:
|
[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. 10.1016/j.disc.2015.04.020 |
| Reference:
|
[15] 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 |
| . |
