TY - JOUR
T1 - Closure operation for even factors on claw-free graphs
AU - Xiong, Liming
PY - 2011/8/28
Y1 - 2011/8/28
N2 - Ryjáček (1997) [6] defined a powerful closure operation cl(G) on claw-free graphs G. Very recently, Ryjáček et al. (2010) [8] have developed the closure operation cl2f(G) on claw-free graphs which preserves the (non)-existence of a 2-factor. In this paper, we introduce a closure operation clse(G) on claw-free graphs that generalizes the above two closure operations. The closure of a graph is unique determined and the closure turns a claw-free graph into the line graph of a graph containing no cycle of length at most 5 and no cycles of length 6 satisfying a certain condition and no induced subgraph being isomorphic to the unique tree with a degree sequence 111133. We show that these closure operations on claw-free graphs all preserve the minimum number of components of an even factor. In particular, we show that a claw-free graph G has an even factor with at most k components if and only if clse(G) (cl(G),cl2f(G), respectively) has an even factor with at most k components. However, the closure operation does not preserve the (non)-existence of a 2-factor.
AB - Ryjáček (1997) [6] defined a powerful closure operation cl(G) on claw-free graphs G. Very recently, Ryjáček et al. (2010) [8] have developed the closure operation cl2f(G) on claw-free graphs which preserves the (non)-existence of a 2-factor. In this paper, we introduce a closure operation clse(G) on claw-free graphs that generalizes the above two closure operations. The closure of a graph is unique determined and the closure turns a claw-free graph into the line graph of a graph containing no cycle of length at most 5 and no cycles of length 6 satisfying a certain condition and no induced subgraph being isomorphic to the unique tree with a degree sequence 111133. We show that these closure operations on claw-free graphs all preserve the minimum number of components of an even factor. In particular, we show that a claw-free graph G has an even factor with at most k components if and only if clse(G) (cl(G),cl2f(G), respectively) has an even factor with at most k components. However, the closure operation does not preserve the (non)-existence of a 2-factor.
KW - Claw-free graph
KW - Closure
KW - Even factor
KW - Supereulerian
UR - http://www.scopus.com/inward/record.url?scp=79959223818&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2011.04.009
DO - 10.1016/j.disc.2011.04.009
M3 - Article
AN - SCOPUS:79959223818
SN - 0012-365X
VL - 311
SP - 1714
EP - 1723
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 16
ER -