×

Two operations on a graph preserving the (non)existence of 2-factors in its line graph. (English) Zbl 1349.05177

Summary: Let \(G=(V(G),E(G))\) be a graph. R. J. Gould and E. A. Hynds [Bull. Inst. Comb. Appl. 26, 46–48 (1999; Zbl 0922.05046)] showed a well-known characterization of \(G\) by its line graph \(L(G)\) with 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 \text{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 [G. Li and Z. Liu, Syst. Sci. Math. Sci. 8, No. 4, 369–372 (1995; Zbl 0851.05084); R. Tian et al., Discrete Math. 312, No. 21, 3140–3145 (2012; Zbl 1251.05145)], and is the best possible.

MSC:

05C35 Extremal problems in graph theory
05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs
05C76 Graph operations (line graphs, products, etc.)
05C40 Connectivity
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] J. A. Bondy, U. S. R. Murty: Graph Theory with Applications. American Elsevier Publishing Co., New York, 1976.
[2] S. A. Choudum, M. S. Paulraj: Regular factors in K 1,3-free graphs. J. Graph Theory 15 (1991), 259–265. · Zbl 0756.05087 · doi:10.1002/jgt.3190150304
[3] Y. Egawa, K. Ota: Regular factors in K 1,n -free graphs. J. Graph Theory 15 (1991), 337–344. · Zbl 0756.05088 · doi:10.1002/jgt.3190150310
[4] R. J. Gould, E. A. Hynds: A note on cycles in 2-factors of line graphs. Bull. Inst. Comb. Appl. 26 (1999), 46–48. · Zbl 0922.05046
[5] G. Li, Z. Liu: On 2-factors in claw-free graphs. Syst. Sci. Math. Sci. 8 (1995), 369–372. · Zbl 0851.05084
[6] Z. Ryjáček: On a closure concept in claw-free graphs. J. Comb. Theory, Ser. B 70 (1997), 217–224. · Zbl 0872.05032 · doi:10.1006/jctb.1996.1732
[7] Z. Ryjáček, A. Saito, R. H. Schelp: Closure, 2-factors, and cycle coverings in claw-free graphs. J. Graph Theory 32 (1999), 109–117. · Zbl 0932.05045 · doi:10.1002/(SICI)1097-0118(199910)32:2<109::AID-JGT1>3.0.CO;2-O
[8] R. Tian, L. Xiong, Z. Niu: On 2-factors in claw-free graphs whose edges are in small cycles. Discrete Math. 312 (2012), 3140–3145. · Zbl 1251.05145 · doi:10.1016/j.disc.2012.07.005
[9] K. Yoshimoto: On the number of components in 2-factors of claw-free graphs. Discrete Math. 307 (2007), 2808–2819. · Zbl 1129.05037 · doi:10.1016/j.disc.2006.11.022
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.