Open Journal of Discrete Mathematics
Vol.4 No.2(2014), Article ID:44688,9 pages DOI:10.4236/ojdm.2014.42004

General Cyclic Orthogonal Double Covers of Finite Regular Circulant Graphs

Ramadan El-Shanawany, Hanan Shabana

Department of Physics and Engineering Mathematics, Faculty of Electronic Engineering, Menoufiya University, Menouf, Egypt

Email: ramadan_elshanawany380@yahoo.com, the_engineer_hanan@yahoo

Copyright © 2014 by authors and Scientific Research Publishing Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

Received 20 January 2014; revised 18 February 2014; accepted 15 March 2014

ABSTRACT

An orthogonal double cover (ODC) of a graph H is a collection of subgraphs (pages) of H, so that they cover every edge of H twice and the intersection of any two of them contains exactly one edge. An ODC of H is cyclic (CODC) if the cyclic group of order is a subgroup of the automorphism group of. In this paper, we introduce a general orthogonal labelling for CODC of circulant graphs and construct CODC 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.

Keywords:Graph Decomposition, Cyclic Orthogonal Double Cover, Automorphism Group, Orthogonal Labelling

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

References

  1. Gronau, H.-D.O.F., Hartmann, S., Grüttmüller, M., Leck, U. and Leck, V. (2002) On Orthogonal Double Covers of Graphs. Design Codes Cryptography, 27, 49-91. http://dx.doi.org/10.1023/A:1016546402248
  2. El-Shanawany, R. and Higazy, M. (2008) Orthogonal Double Covers of Complete Graphs by Certain Spanning Subgraphs. Australasian Journal of Combinatorics, 42, 223-228.
  3. El Shanawany, R., Higazy, M. and Scapellato, R. (2010) A Note on Orthogonal Double Covers of Complete Bipartite Graphs by a Special Class of Six Caterpillars. AKCE International Journal of Graphs and Combinatorics, 7, 1-4.
  4. El-Shanawany, R.A., Higazy, M.S. and Scapellato, R. (2009) Orthogonal Double Covers of Complete Bipartite Graphs by the Union of a Cycle and a Star. Australasian Journal of Combinatorics, 43, 281-293.
  5. El-Shanawany, R. and Higazy, M. (2007) General Symmetric Starter of Orthogonal Double Covers of Complete Bipartite Graph. International Journal of Mathematics and Mathematical Sciences, 2007, Article ID: 42892. http://dx.doi.org/10.1155/2007/42892
  6. El Shanawany, R., Higazy, M. and El Mesady, A. (2013) On Cartesian Products of Orthogonal Double Covers. International Journal of Mathematics and Mathematical Sciences, 2013, Article ID: 265136.
  7. Scapellato, R., El-Shanawany, R. and Higazy, M. (2009) Orthogonal Double Covers of Cayley Graphs. Discrete Applied Mathematics, 157, 3111-3118. http://dx.doi.org/10.1016/j.dam.2009.06.005
  8. Hartmann, S. and Schumacher, U. (2004) Orthogonal Double Covers of General Graphs. Discrete Applied Mathematics, 138, 107-116. http://dx.doi.org/10.1016/S0166-218X(03)00274-9
  9. Sampathkumar, R. and Sriram, V. (2008) Orthogonal σ-Labelling of Graphs. AKCE International Journal of Graphs and Combinatorics, 5, 57-60.
  10. Sampathkumar, R. and Srinivasan, S. (2011) Cyclic Orthogonal Double Covers of 4-Regular Circulant Graphs. Discrete Mathematics, 311, 2417-2422. http://dx.doi.org/10.1016/j.disc.2011.06.021
  11. El Shanawany, R., and Shabana, H. (2014) On Orthogonal Double Covers of Circulant Graphs. British Journal of Mathematics & Computer Science, 4, 394-401.
  12. Balakrishnan, R. and Ranganathan, K. (2012) A Textbook of Graph Theory. Springer, Berlin. http://dx.doi.org/10.1007/978-1-4614-4529-6
  13. Gronau, H.-D.O.F., Mullin, R.C. and Rosa, A. (1997) On Orthogonal Double Covers of Complete Graphs by Trees. Graphs and Combinatorics, 13, 251-262.