TY - JOUR
T1 - Closure, stability and iterated line graphs with a 2-factor
AU - Saito, Akira
AU - Xiong, Liming
PY - 2009/8/28
Y1 - 2009/8/28
N2 - We consider 2-factors with a bounded number of components in the n-times iterated line graph Ln (G). We first give a characterization of graph G such that Ln (G) has a 2-factor containing at most k components, based on the existence of a certain type of subgraph in G. This generalizes the main result of [L. Xiong, Z. Liu, Hamiltonian iterated line graphs, Discrete Math. 256 (2002) 407-422]. We use this result to show that the minimum number of components of 2-factors in the iterated line graphs Ln (G) is stable under the closure operation on a claw-free graph G. This extends results in [Z. Ryjáček, On a closure concept in claw-free graphs, J. Combin. Theory Ser. B 70 (1997) 217-224; 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; L. Xiong, Z. Ryjáček, H.J. Broersma, On stability of the hamiltonian index under contractions and closures, J. Graph Theory 49 (2005) 104-115].
AB - We consider 2-factors with a bounded number of components in the n-times iterated line graph Ln (G). We first give a characterization of graph G such that Ln (G) has a 2-factor containing at most k components, based on the existence of a certain type of subgraph in G. This generalizes the main result of [L. Xiong, Z. Liu, Hamiltonian iterated line graphs, Discrete Math. 256 (2002) 407-422]. We use this result to show that the minimum number of components of 2-factors in the iterated line graphs Ln (G) is stable under the closure operation on a claw-free graph G. This extends results in [Z. Ryjáček, On a closure concept in claw-free graphs, J. Combin. Theory Ser. B 70 (1997) 217-224; 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; L. Xiong, Z. Ryjáček, H.J. Broersma, On stability of the hamiltonian index under contractions and closures, J. Graph Theory 49 (2005) 104-115].
KW - 2-factor
KW - Claw-free graph
KW - Closure operation
KW - Iterated line graph
UR - http://www.scopus.com/inward/record.url?scp=67651152614&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2009.03.003
DO - 10.1016/j.disc.2009.03.003
M3 - Article
AN - SCOPUS:67651152614
SN - 0012-365X
VL - 309
SP - 5000
EP - 5010
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 16
ER -