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.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.