Let X and G be graphs, such that G is isomorphic to a subgraph of X. An orthogonal double cover (ODC) of X by G is a collection B D of subgraphs of X, all isomorphic with G, such that (i) every edge of X occurs in exactly two members of B and (ii) two members of G share an edge if and only if x and y are adjacent in X. The main question is: given the pair (X, G), is there an ODC of X by G? An obvious necessary condition is that X is regular. A technique to construct ODCs for Cayley graphs is introduced. It is shown that for all (X, G) where X is a 3-regular Cayley graph on an abelian group there is an ODC, a few well known exceptions apart.

Orthogonal double covers of Cayley graphs

SCAPELLATO, RAFFAELE;
2009-01-01

Abstract

Let X and G be graphs, such that G is isomorphic to a subgraph of X. An orthogonal double cover (ODC) of X by G is a collection B D of subgraphs of X, all isomorphic with G, such that (i) every edge of X occurs in exactly two members of B and (ii) two members of G share an edge if and only if x and y are adjacent in X. The main question is: given the pair (X, G), is there an ODC of X by G? An obvious necessary condition is that X is regular. A technique to construct ODCs for Cayley graphs is introduced. It is shown that for all (X, G) where X is a 3-regular Cayley graph on an abelian group there is an ODC, a few well known exceptions apart.
2009
Cayley graph; Graph decomposition; Orthogonal double cover Symmetric starter
File in questo prodotto:
File Dimensione Formato  
DAM7379.pdf

Accesso riservato

: Post-Print (DRAFT o Author’s Accepted Manuscript-AAM)
Dimensione 969 kB
Formato Adobe PDF
969 kB Adobe PDF   Visualizza/Apri

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: https://hdl.handle.net/11311/546657
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 17
  • ???jsp.display-item.citation.isi??? 17
social impact