Two operations on a graph preserving the (non)existence of 2-factors in its line graph
Mingqiang An; Hong-Jian Lai; Hao Li; Guifu Su; Runli Tian; Liming Xiong
Czechoslovak Mathematical Journal (2014)
- Volume: 64, Issue: 4, page 1035-1044
- ISSN: 0011-4642
Access Full Article
topAbstract
topHow to cite
topAn, Mingqiang, et al. "Two operations on a graph preserving the (non)existence of 2-factors in its line graph." Czechoslovak Mathematical Journal 64.4 (2014): 1035-1044. <http://eudml.org/doc/269841>.
@article{An2014,
abstract = {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[\lbrace y\in V(G)\; 1\le \{\rm dist\}_\{G\}(x,y)\le 2\rbrace ]$ 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.},
author = {An, Mingqiang, Lai, Hong-Jian, Li, Hao, Su, Guifu, Tian, Runli, Xiong, Liming},
journal = {Czechoslovak Mathematical Journal},
keywords = {2-factor; claw-free graph; line graph; $N^\{2\}$-locally connected; 2-factor; claw-free graph; line graph; $N^\{2\}$-locally connected},
language = {eng},
number = {4},
pages = {1035-1044},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Two operations on a graph preserving the (non)existence of 2-factors in its line graph},
url = {http://eudml.org/doc/269841},
volume = {64},
year = {2014},
}
TY - JOUR
AU - An, Mingqiang
AU - Lai, Hong-Jian
AU - Li, Hao
AU - Su, Guifu
AU - Tian, Runli
AU - Xiong, Liming
TI - Two operations on a graph preserving the (non)existence of 2-factors in its line graph
JO - Czechoslovak Mathematical Journal
PY - 2014
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 64
IS - 4
SP - 1035
EP - 1044
AB - 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[\lbrace y\in V(G)\; 1\le {\rm dist}_{G}(x,y)\le 2\rbrace ]$ 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.
LA - eng
KW - 2-factor; claw-free graph; line graph; $N^{2}$-locally connected; 2-factor; claw-free graph; line graph; $N^{2}$-locally connected
UR - http://eudml.org/doc/269841
ER -
References
top- 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
- 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, G., Liu, Z., On 2-factors in claw-free graphs, Syst. Sci. Math. Sci. 8 (1995), 369-372. (1995) Zbl0851.05084MR1374533
- 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., 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
- Tian, R., Xiong, L., Niu, Z., 10.1016/j.disc.2012.07.005, Discrete Math. 312 (2012), 3140-3145. (2012) Zbl1251.05145MR2957934DOI10.1016/j.disc.2012.07.005
- 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.