×

Orthogonal double covers of 4-regular circulant graphs. (English) Zbl 1339.05262

Summary: An orthogonal double cover (ODC) of a graph \(H\) is a collection \(\mathcal{G}=\{G_v: v\in V(H)\}\) of \(|V(H)|\) subgraphs of \(H\) such that every edge of \(H\) is contained in exactly two members of \(\mathcal{G}\) and for any two members \(G_u\) and \(G_v\) in \(\mathcal{G},\) \(|E(G_u)\cap E(G_v)|\) is 1 if \(u\) and \(v\) are adjacent in \(H\) and it is 0 if \(u\) and \(v\) are nonadjacent in \(H\). An ODC \(\mathcal{G}\) of \(H\) is cyclic if the cyclic group of order \(\mid V(H) \mid\) is a subgroup of the automorphism group of \(\mathcal{G}\); otherwise it is noncyclic. Recently, R. Sampathkumar and S. Srinivasan [Discrete Math. 311, No. 21, 2417–2422 (2011; Zbl 1239.05154)] settled the problem of the existence of cyclic ODCs of 4-regular circulant graphs. In this paper, we concerned with noncyclic ODCs of such graphs, whenever cyclic ODC does not exist.

MSC:

05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Citations:

Zbl 1239.05154