2-factors in claw-free graphs with locally disconnected vertices
Mingqiang An; Liming Xiong; Runli Tian
Czechoslovak Mathematical Journal (2015)
- Volume: 65, Issue: 2, page 317-330
- ISSN: 0011-4642
Access Full Article
topAbstract
topHow to cite
topAn, Mingqiang, Xiong, Liming, and Tian, Runli. "2-factors in claw-free graphs with locally disconnected vertices." Czechoslovak Mathematical Journal 65.2 (2015): 317-330. <http://eudml.org/doc/270132>.
@article{An2015,
abstract = {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).},
author = {An, Mingqiang, Xiong, Liming, Tian, Runli},
journal = {Czechoslovak Mathematical Journal},
keywords = {claw-free graph; 2-factor; closure; locally disconnected vertex; singular edge},
language = {eng},
number = {2},
pages = {317-330},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {2-factors in claw-free graphs with locally disconnected vertices},
url = {http://eudml.org/doc/270132},
volume = {65},
year = {2015},
}
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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 65
IS - 2
SP - 317
EP - 330
AB - 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).
LA - eng
KW - claw-free graph; 2-factor; closure; locally disconnected vertex; singular edge
UR - http://eudml.org/doc/270132
ER -
References
top- Bielak, H., 10.1016/S0012-365X(99)00163-6, Discrete Math. 213 (2000), 21-24. (2000) Zbl0951.05069MR1755406DOI10.1016/S0012-365X(99)00163-6
- Bondy, J. A., Murty, U. S. R., Graph Theory with Applications, American Elsevier Publishing Co. New York (1976). (1976) MR0411988
- Choudum, S. A., Paulraj, M. S., 10.1002/jgt.3190150304, J. Graph Theory 15 (1991), 259-265. (1991) MR1111989DOI10.1002/jgt.3190150304
- Egawa, Y., Ota, K., 10.1002/jgt.3190150310, J. Graph Theory 15 (1991), 337-344. (1991) MR1111995DOI10.1002/jgt.3190150310
- Faudree, J. R., Faudree, R. J., Ryjáček, Z., Forbidden subgraphs that imply 2-factors, Discrete Math. 308 (2008), 1571-1582. (2008) Zbl1139.05049MR2392597
- Gould, R. J., Hynds, E. A., A note on cycles in 2-factors of line graphs, Bull. Inst. Comb. Appl. 26 (1999), 46-48. (1999) Zbl0922.05046MR1683819
- Li, M., Hamiltonian cycles in -locally connected claw-free graphs, Ars Comb. 62 (2002), 281-288. (2002) MR1881966
- Oberly, D. J., Sumner, D. P., 10.1002/jgt.3190030405, J. Graph Theory 3 (1979), 351-356. (1979) MR0549691DOI10.1002/jgt.3190030405
- Pfender, F., 10.1002/jgt.20080, J. Graph Theory 49 (2005), 262-272. (2005) Zbl1068.05042MR2197229DOI10.1002/jgt.20080
- Ryjáček, Z., 10.1006/jctb.1996.1732, J. Comb. Theory, Ser. B 70 (1997), 217-224. (1997) MR1459867DOI10.1006/jctb.1996.1732
- Ryjáček, Z., 10.1002/jgt.3190140305, J. Graph Theory 14 (1990), 321-331. (1990) MR1060860DOI10.1002/jgt.3190140305
- Ryjáček, Z., Saito, A., Schelp, R. H., 10.1002/(SICI)1097-0118(199910)32:2<109::AID-JGT1>3.0.CO;2-O, J. Graph Theory 32 (1999), 109-117. (1999) Zbl0932.05045MR1709653DOI10.1002/(SICI)1097-0118(199910)32:2<109::AID-JGT1>3.0.CO;2-O
- Ryjáček, Z., Xiong, L., Yoshimoto, K., 10.1016/j.disc.2010.02.004, Discrete Math. 310 (2010), 1573-1579. (2010) Zbl1225.05208MR2601267DOI10.1016/j.disc.2010.02.004
- Tian, R., Xiong, L., 10.1016/j.disc.2015.04.020, (to appear) in Discrete Math. DOI:10.1016/j.disc.2015.04.020. DOI10.1016/j.disc.2015.04.020
- Yoshimoto, K., 10.1016/j.disc.2006.11.022, Discrete Math. 307 (2007), 2808-2819. (2007) Zbl1129.05037MR2362964DOI10.1016/j.disc.2006.11.022
NotesEmbed ?
topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.