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 graphG, 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.
Even cycles and even 2-factors in the line graph of a simple graph / Bonisoli, Arrigo; Bonvicini, Simona. - In: ELECTRONIC JOURNAL OF COMBINATORICS. - ISSN 1077-8926. - 24:4(2017), pp. P4.15-P4.15.
Even cycles and even 2-factors in the line graph of a simple graph
BONISOLI, Arrigo;BONVICINI, Simona
2017
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 graphG, 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.File | Dimensione | Formato | |
---|---|---|---|
line_graphs_ECD_revised_060516.pdf
Open access
Descrizione: Articolo principale
Tipologia:
AAM - Versione dell'autore revisionata e accettata per la pubblicazione
Dimensione
252 kB
Formato
Adobe PDF
|
252 kB | Adobe PDF | Visualizza/Apri |
VOR_Even cycles and even 2-factors.pdf
Open access
Tipologia:
VOR - Versione pubblicata dall'editore
Dimensione
317.95 kB
Formato
Adobe PDF
|
317.95 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris