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.

DOI: 10.4236/ojdm.2014.42004                

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 G of H is cyclic (CODC) if the cyclic group of order is a subgroup of the automorphism group of G. 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

Conflicts of Interest

The authors declare no conflicts of interest.

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.