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

Abstract

top
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 ) 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).

How to cite

top

An, 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
  1. Bielak, H., 10.1016/S0012-365X(99)00163-6, Discrete Math. 213 (2000), 21-24. (2000) Zbl0951.05069MR1755406DOI10.1016/S0012-365X(99)00163-6
  2. Bondy, J. A., Murty, U. S. R., Graph Theory with Applications, American Elsevier Publishing Co. New York (1976). (1976) MR0411988
  3. Choudum, S. A., Paulraj, M. S., 10.1002/jgt.3190150304, J. Graph Theory 15 (1991), 259-265. (1991) MR1111989DOI10.1002/jgt.3190150304
  4. Egawa, Y., Ota, K., 10.1002/jgt.3190150310, J. Graph Theory 15 (1991), 337-344. (1991) MR1111995DOI10.1002/jgt.3190150310
  5. Faudree, J. R., Faudree, R. J., Ryjáček, Z., Forbidden subgraphs that imply 2-factors, Discrete Math. 308 (2008), 1571-1582. (2008) Zbl1139.05049MR2392597
  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. (1999) Zbl0922.05046MR1683819
  7. Li, M., Hamiltonian cycles in N 2 -locally connected claw-free graphs, Ars Comb. 62 (2002), 281-288. (2002) MR1881966
  8. Oberly, D. J., Sumner, D. P., 10.1002/jgt.3190030405, J. Graph Theory 3 (1979), 351-356. (1979) MR0549691DOI10.1002/jgt.3190030405
  9. Pfender, F., 10.1002/jgt.20080, J. Graph Theory 49 (2005), 262-272. (2005) Zbl1068.05042MR2197229DOI10.1002/jgt.20080
  10. Ryjáček, Z., 10.1006/jctb.1996.1732, J. Comb. Theory, Ser. B 70 (1997), 217-224. (1997) MR1459867DOI10.1006/jctb.1996.1732
  11. Ryjáček, Z., 10.1002/jgt.3190140305, J. Graph Theory 14 (1990), 321-331. (1990) MR1060860DOI10.1002/jgt.3190140305
  12. 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
  13. 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
  14. 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
  15. 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 ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.