We show that a digraph which contains a directed 2-factor and has minimum in-degree and outdegree at least four has two non-isomorphic directed 2-factors. As a corollary, we deduce that every graph which contains a 2-factor and has minimum degree at least eight has two non-isomorphic 2-factors. In addition we construct: an infinite family of 3-diregular digraphs with the property that all their directed 2-factors are Hamilton cycles, an infinite family of 2-connected 4-regular graphs with the property that all their 2-factors are isomorphic, and an infinite family of cyclically 6-edge-connected cubic graphs with the property that all their 2-factors are Hamilton cycles.

Graphs and Digraphs with all 2-factors isomorphic

ABREU, Marien;FUNK, Martin;LABBATE, Domenico;
2004

Abstract

We show that a digraph which contains a directed 2-factor and has minimum in-degree and outdegree at least four has two non-isomorphic directed 2-factors. As a corollary, we deduce that every graph which contains a 2-factor and has minimum degree at least eight has two non-isomorphic 2-factors. In addition we construct: an infinite family of 3-diregular digraphs with the property that all their directed 2-factors are Hamilton cycles, an infinite family of 2-connected 4-regular graphs with the property that all their 2-factors are isomorphic, and an infinite family of cyclically 6-edge-connected cubic graphs with the property that all their 2-factors are Hamilton cycles.
File in questo prodotto:
File Dimensione Formato  
doi_10.1016_j.jctb.2004.09.004.pdf

non disponibili

Tipologia: Documento in Post-print
Licenza: DRM non definito
Dimensione 200.21 kB
Formato Adobe PDF
200.21 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11563/16638
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 11
social impact