Let H be a graph on n vertices and G a collection of n subgraphs of H, one for each vertex. Then G is an orthogonal double cover (ODC)of H if every edge of H occurs in exactly two members of G and any two members of G share exactly an edge whenever the corresponding vertices are adjacent in H. If all subgraphs in G are isomorphic to a given spanning subgraph G, then G is said to be an ODC of H by G. We construct ODCs of the complete bipartite graph H=K(n,n) by the union of a m-cycle and a (n-m)-star whose central vertex belongs to that cycle and m = 6, 8, 10, 12 with m < n. Furthermore, we construct ODCs of H = K(n,n) by the disjoint union of a m-cycle and a (n-m)-star where m = 4,8 and m < n. In all cases, G is a symmetric starter of the cyclic group of order n. In addition, we introduce a generalization of this result.

Orthogonal double covers of complete bipartite graphs by the union of a cycle and a star

SCAPELLATO, RAFFAELE
2009-01-01

Abstract

Let H be a graph on n vertices and G a collection of n subgraphs of H, one for each vertex. Then G is an orthogonal double cover (ODC)of H if every edge of H occurs in exactly two members of G and any two members of G share exactly an edge whenever the corresponding vertices are adjacent in H. If all subgraphs in G are isomorphic to a given spanning subgraph G, then G is said to be an ODC of H by G. We construct ODCs of the complete bipartite graph H=K(n,n) by the union of a m-cycle and a (n-m)-star whose central vertex belongs to that cycle and m = 6, 8, 10, 12 with m < n. Furthermore, we construct ODCs of H = K(n,n) by the disjoint union of a m-cycle and a (n-m)-star where m = 4,8 and m < n. In all cases, G is a symmetric starter of the cyclic group of order n. In addition, we introduce a generalization of this result.
2009
graph decompositions; symmetric starter; orthogonal double cover
File in questo prodotto:
File Dimensione Formato  
ajc_v43_p281-293.pdf

Accesso riservato

: Post-Print (DRAFT o Author’s Accepted Manuscript-AAM)
Dimensione 147.42 kB
Formato Adobe PDF
147.42 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/546668
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? ND
social impact