On Orthogonal Double Covers of Circulant Graphs
R. El-Shanawany
Department of physics and Engineering Mathematics, Faculty of Electronic Engineering, Menoufiya University, Menouf, Egypt.
H. Shabana *
Department of physics and Engineering Mathematics, Faculty of Electronic Engineering, Menoufiya University, Menouf, Egypt.
*Author to whom correspondence should be addressed.
Abstract
Let X be a graph on n vertices and let B = {P(x) : x ∈ V (X)} be a collection of n subgraphs of X, one for each vertex, B is an orthogonal double cover (ODC) of X if every edge of X occurs in exactly two members of B and any two members share an edge whenever the corresponding vertices are adjacent in X and share no edges whenever the corresponding vertices are nonadjacent 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 a regular. In this paper, we are almost exclusively concerned with the starter maps of the orthogonal double covers of cayley graphs and using this method to construct ODCs by a complete bipartite graph, a complete tripartite graph, caterpillar, and a connected union of a cycle and a star whose center vertex belongs to that cycle.
Keywords: Cayley graph, Graph decomposition, Orthogonal double cover, Symmetric starter.