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.
2017
24
4
P4.15
P4.15
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.
Bonisoli, Arrigo; Bonvicini, Simona
File in questo prodotto:
File Dimensione Formato  
line_graphs_ECD_revised_060516.pdf

Open access

Descrizione: Articolo principale
Tipologia: 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: Versione pubblicata dall'editore
Dimensione 317.95 kB
Formato Adobe PDF
317.95 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Licenza Creative Commons
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

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1146051
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 5
social impact