General Cyclic Orthogonal Double Covers of Finite Regular Circulant Graphs ()
1. Introduction
All graphs we deal with are undirected, finite and simple. Let
be any regular graph, and let
be a collection of
subgraphs (pages) of
. The collection
is an orthogonal double cover (ODC) of
if it has the following properties:
1) Double cover property:
Every edge of
is contained in exactly two of the pages in
.
2) Orthogonality property:
For any two distinct pages
and
,
if and only if i and j are adjacent in
.
If all pages
for all
then
is an ODC of
by
. An automorphism of an ODC
of
is a permutation
such that
where for
is a subgraph of
with
and
According to the obvious properties of ODCs by a graph
, the underlying graph H has to be
-regular. This concept is a generalization of the definitions of an ODC of complete graphs and complete bipartite graphs, which has been studied extensively [1] -[2] . El-Shanawny et al. studied extensively the ODC of complete bipartite graphs; see [3] -[6] . An effective method to construct ODCs in the above cases was based on the idea of translate a given subgraph
by a group acting on
If the cyclic group of order
is a subgroup of the automorphism group of
(the set of all automorphisms of
), then an ODC
of
is cyclic (CODC). Therefore, the circulant graph is of special interest. In [7] , Scapellato et al. offers some insights on the case on ODC of Cayley graphs on cyclic groups. In [8] , Hartmann and Schumacher proved the following: 1) Let
be a 2-regular graph. There exists an ODC of
by
with three exceptions for
:
and
, 2) Let
be a 3-regular graph containing a 1-factor and without a component isomorphic to
. There exists an ODC of
by
, 3) Let
be a 3-regular graph containing a 1-factor and
. There exists an ODC of
by
. In [9] , Sampathkumar et al. introduced a special kind of orthogonal labelling called orthogonal σ-labelling, and they found it for some caterpillars of diameters 4. In [7] , Scapellato et al. studied the ODC of Cayley graphs and proved the following: 1) All 3-regular Cayley graphs, except
, have ODCs by
, 2) All 3-regular Cayley graphs on Abelian groups, except
, have ODCs by
3) All 3-regular Cayley graphs on Abelian groups, except
and the
- prism (Cartesian product of
and
), have ODCs by
In [10] , Sampathkumar et al. completely settled the existence problem of CODCs of 4-regular circulant graphs.
The above results on ODCs of graphs with lower degrees motivate us to consider CODCs of graphs with higher degrees. In [11] , El-Shanawny et al. deal with cayley graphs on abelian groups and proved the existence of ODCs of cayley graphs by several classes of graphs. Here we are concerned with CODCs of circulant graphs of finite degrees higher than
. The paper is organized as follows, Section 1.1 describes the method that can be used throughout. Section-2 constructs CODCs of circulant graphs of finite degrees higher than
by certain graph classes. Section 3 offers the general CODCs of circulant graphs.
Definition 1. For a sequence
of positive integers with
, the circulant graph
, has vertex set
; two vertices
and
are adjacent, if and only if
for some
, 
For an edge
in
, the length of
is
Given two edges
and
of the same length
in
, the rotation distance
between
and
is
where addition and difference are calculated inside
Note that if
then the edges
and
are adjacent; if
then the edges
and
are non adjacent.
Throughout the paper we make use of the usual notation:
for the complete graph on
vertices,
for the complete bipartite graph with independent sets of sizes
and
,
for the path on
vertices,
for the cycle on
vertices,
for the disjoint union
of
and
,
for
disjoint copies of
and
for the union of
and
with a common vertex
belongs to
and
Let
be positive integers,
and
for
the caterpillar
is the tree obtained from the path
by joining vertex
to
new vertices,
Other terminology not defined here can be found in [12] .
CODC of Circulant Graphs
Consider the complete graph
The authors of [13] introduced the notion of an orthogonal labelling. Given a graph
with
edges, a
mapping
is an orthogonal labelling of
if the following conditions are satisfied:
1) For every
,
contains exactly two edges of length
, and exactly one edge of length
if
is even, and 2) For every 
The following theorem of Gronau et al. [13] relates CODCs of
and orthogonal labellings.
Theorem 2. ([13] ) A CODC of
by a graph
exists if and only if there exists an orthogonal labelling of
.
Sampathkumar and Srinivasan [10] , called an orthogonal
-labelling and generalized it to an orthogonal
-labelling, where
is a sequence of positive integers with
.
1) Either n is odd or even and 
Given a subgraph
of
with
edges, a labelling of
in
, is an orthogonal
-labelling of
if:
a) For every
,
contains exactly two edges of length
, and b) 
2)
is even and 
Given a subgraph
of
with
edges, a labelling of
in
, is an orthogonal
-labelling of
if:
a) For every
,
contains exactly two edges of length
, and
contains exactly one edges of length
, and b)
, The following theorem of Sampathkumar and Simaringa [10] , is a generalization of Theorem 2.
Theorem 3 ([10] ). A CODC of
by a graph
exists, if and only if there exists an orthogonal
-labelling of 
2. CODCs of Circulant Graphs by Certain Graph Classes
This section is devoted to constructing the cyclic orthogonal double covers (CODCs) of circulant graphs by different classes of graphs, complete bipartite graph as in Section 2.1, the union of the co-cycles graph with a star, the center vertex of which, belongs to the co-cycles graph as in Section 2.2 and graphs that are connected by a one vertex as in Section 2.3.
2.1. CODCs by a Complete Bipartite Graph
Theorem 4. For any positive integers
such that
, there exists a CODC of
-regular
by
.
Proof Let us define
by
for
and
for
Then the edges of length
where
where
is defined for
. For every
contains exactly two edges of length
, and
, and hence
has an orthogonal labelling. By Theorem 3, there exists a CODC Of
-regular
by
.
Let us define
to be the co-cycles graph (the union of
cycles of length
with a one vertex
in common). In the following section we construct a CODCs of finite regular circulant graphs by
(the union of co-cycles graph with a star whose center vertex is the vertex
).
2.2. CODCs of Circulant Graph by 
Theorem 5 For any positive integer
there exists a CODC of
-regular
by 
Proof Let us define
by
for
where,
,
,
,
,
,
,
,
,
,
,
and
. Then the edges of length
are
and
; those of length
are
and
those of length
are
and
those of length
are
and
; those of length
are
and
those of length
are
and
those of length
are
and
those of length 8 are
and
the edges of length l where
are
and
For every
contains exactly two edges of length
and
and then
and hence
has an orthogonal labelling. By Theorem 3, there exists a CODC of
-regular
by
for
Theorem 6 For any positive integer
, there exists a CODC of
-regular
by
.
Proof Let us define
by
for
where
,
,
and
. Then the edges of length
are
and
those of length
are
and
; those of length
are
and
the edges of length
where
are
and
. For every
,
contains exactly two edges of length
, and since every two edges of the same length are adjacent then
and hence
has an orthogonal labelling. By Theorem 3, there exists a CODC of
-regular
by
for
.
Theorem 7 For any positive integer
, there exists a CODC of
-regular
by
.
Proof Let us define
by
for
,
,
,
,
Then the edges of length
are
and
those of length
are
and
those of length 3 are
and
the edges of length
where
are
and
For every
contains exactly two edges of length
, and since every two edges of the same length are adjacent then
and hence
has an orthogonal labelling. By Theorem 3, there exists a CODC of
-regular
by
for
.
Theorem 8 For any positive integer
there exists a CODC of
-regular
by
.
Proof Let us define
by
for
,
,
,
and
Then the edges of length
are
and
those of length
are
and
those of length
are
and
those of length
are
and
the edges of length
where
are
and
. For every
contains exactly two edges of length
, and since every two edges of the same length are adjacent then
and hence
has an orthogonal labelling. By Theorem 3, there exists a CODC of
-regular
by
for
.
Theorem 9 For any positive integer
there exists a CODC of
-regular
by
.
Proof Let us define
by
for
,
, and
. Then the edges of length
are
and
those of length
are
and
those of length
are
and
those of length
are
and
those of length
are
and
the edges of length
where
are
and
For every
,
contains exactly two edges of length
, and since every two edges of the same length are adjacent then
and hence
has an orthogonal labelling. By theorem 3, there exists a CODC of
-regular
by
for
.
According to these results, we can pose the following conjecture:
Conjecture 1. For any positive integers
such that
and
, there exists a CODC of
-regular
by
.
2.3. CODCs by
Graphs that Are Connected by a One Vertex a
Theorem 10 For any positive integer
there exists a CODC of
-regular
by
.
Proof Let us define
by
for
,
,
,
and
. Then the edges of length
are
and
; those of length
are
and
; those of length
are
and
those of length
are
and
the edges of length
where
are
and
For every
contains exactly two edges of length
, and since every two edges of the same length are adjacent then
and hence
has an orthogonal labelling. By Theorem 3, there exists a CODC of
-regular
by
for
.
Theorem 11 For any prime number
there exists a CODC of
-regular
by
.
Proof Let us define
by
for
,
,
,
and
. Then the edges of length
are
and
those of length
are
and
; those of length
are
and
the edges of length
where
are
and
. For every
contains exactly two edges of length
, and since every two edges of the same length are adjacent then
and hence
has an orthogonal labelling. By Theorem 3, there exists a CODC of
-regular
by
for
.
Theorem 12 For any positive integer
there exists a CODC of
-regular
by
.
Proof Let us define
by
for
,
,
,
,
and
Then the edges of length
are
and
those of length
are
and
those of length
are
and
the edges of length
where
are
and
For every
contains exactly two edges of length
, and since every two edges of the same length are adjacent then
and hence
has an orthogonal labelling. By Theorem 3, there exists a CODC of
-regular
by
for
.
Conjecture 2. For any positive integers
so that
, there exists a CODC of
-regular
by
.
3. General CODCs of Circulant Graph
In constructing CODCs a natural approach is to try to use given CODCs to obtain CODCs of a larger Circulant Graph. That is we will do in the following theorem.
Theorem 13 For any positive integers
if there exists a CODC of
by G with respect to
Then there exists a CODC of
where
by
with respect to
.
Proof Let the
has a CODC by
with respect to
. Then the graph
has an orthogonal
-labelling with respect to
. And hence, for every
,
contain exactly two edges of the length
as
and
where
and
. And
to construct a CODC of
for
by
with respect to
, the graph
must have an orthogonal
-labelling with respect to
. From the orthogonal labelling of
we can obtain an orthogonal labelling of
as follows Case 1: Either
is odd or even and 

where
For every
contain exactly two edges of the length
as
and
where

and

By the definition of
,
and
, we have
Then the graph
has an orthogonal
-labelling with respect to
.
Case 2:
is even and 

where
. For every
,
contain exactly two edges of the length
as
and
where

and

By the definition of,
,
and
, we have
Then the graph
has an orthogonal
-labelling with respect to
. By Theorem 3, there exists a CODC of
by
with respect to
.
4. Conclusion
In this paper we are concerned with the orthogonal labelling of CODCs of finite regular circulant graphs. We constructed CODCs by certain classes of graphs such as complete bipartite graph, the union of the co-cycles graph with a star, the center vertex of which belongs to the co-cycles graph and graphs that are connected by a one vertex. Finally we introduced general CODCs of the circulant graph.