Even Cycles and Even 2-Factors in the Line Graph of a Simple Graph

Arrigo Bonisoli, Simona Bonvicini

Abstract


Let $G$ be a connected graph with an even number of edges. We show that if the subgraph of $G$ induced by the vertices of odd degree has a perfect matching, then the line graph of $G$ has a $2$-factor whose connected components are cycles of even length (an even $2$-factor). For a cubic graph $G$, we also give a necessary and sufficient condition so that the corresponding line graph $L(G)$ has an even cycle decomposition of index $3$, i.e., the edge-set of $L(G)$ can be partitioned into three $2$-regular subgraphs whose connected components are cycles of even length. The more general problem of the existence of even cycle decompositions of index $m$ in $2d$-regular graphs is also addressed.


Keywords


Cycle decomposition; 2-factor; Oriented graphs; Line graph

Full Text:

PDF