CYCLIC ORTHOGONAL DOUBLE COVERS OF 6-REGULAR CIRCULANT GRAPHS BY DISCONNECTED FORESTS

CYCLIC ORTHOGONAL DOUBLE COVERS OF 6-REGULAR CIRCULANT GRAPHS BY DISCONNECTED FORESTS

V. Sriram

[PDF]

Abstract

An orthogonal double cover (ODC) of a graph H is a collection G = {Gv : v ∈ V (H)} of |V (H)| subgraphs of H such that every edge of H is contained in exactly two members of G and for any two members Gu and Gv in G, |E(Gu) ∩ E(Gv)| is 1 if u and v are adjacent in H and it is 0 if u and v are nonadjacent in H. An ODC G of H is cyclic if the cyclic group of order |V (H)| is a subgroup of the automorphism group of G; otherwise it is noncyclic. Recently, Sampathkumar and Srinivasan settled the problem of the existence of cyclic ODCs of 4-regular circulant graphs. An ODC G of H is cyclic (CODC) if the cyclic group of order |V(H)| is a subgroup of the automorphism group of G, the set of all automorphisms of G; otherwise it is noncyclic. In this paper, we have completely settled the existence problem of CODCs of 6-regular circulant graphs by four acyclic disconnected graphs.

Keywords

Orthogonal double covers of graphs, Labellings of graphs, Circulant graphs