General Cyclic Orthogonal Double Covers of Finite Regular Circulant Graphs

DOI: 10.4236/ojdm.2014.42004   PDF   HTML   XML   2,955 Downloads   4,339 Views   Citations

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.

Share and Cite:

El-Shanawany, R. and Shabana, H. (2014) General Cyclic Orthogonal Double Covers of Finite Regular Circulant Graphs. Open Journal of Discrete Mathematics, 4, 19-27. doi: 10.4236/ojdm.2014.42004.

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.

  
comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.