On Orthogonal Double Covers of Complete Bipartite Graph by the Disjoint Union of Graphs

El-Serafi, Saied A.; M. Kamel, Magdi; El-Shanawany, Ramadan A.; El-Mesad Y, Ahmed I.

doi:10.21608/mjeer.2018.64678

On Orthogonal Double Covers of Complete Bipartite Graph by the Disjoint Union of Graphs

Document Type : Original Article

Authors

Dept. of Physics and Engineering Mathematics, Faculty of Electronic Engineering, Menoufia University.

10.21608/mjeer.2018.64678

Abstract

The existence problem of the orthogonal double covers of the graphs is a well-known problem in the theory of combinatorial designs. In this paper, we construct the orthogonal double covers of the complete bipartite graph by the disjoint union of paths, copies of a caterpillar, copies of a certain path, and by other certain defined graph. We use the vector method as a helping tool for constructing our results, the advantage of this method is that it is accessible to discrete mathematicians not intimately familiar with the theory of the orthogonal double covers.

References

o; -webkit-text-stroke-width: 0px; "> [1] M. J. Demetrovics, Z. Füredi, and G. O. H. Katona, “Minimum matrix
representations of closure operations”, Discrete Appl. Math, Vol. 11, pp.
115-128, 1985.
[2] J. Demetrovics and G. O. H. Katona, “External combinatorial problems in
relational database”, In Fundamentals of combinatorics of computation
theory, pp. 110-119. Springer, Berlin, 1981.
[3] K. Heinrich, “Graph decompositions and designs, In (C. J. Colbourn and
J. H. Dinitz, eds.), The CRC Handbook of Combinatorial Designs, Chapter
IV. 22”, CRC Press, Boca Raton, 1996.
[4] R. Scapellato, R. El-Shanawany and M. Higazy, “Orthogonal double
covers of Cayley graphs”, Discrete Appl. Math, Vol. 157, pp. 3111-3118,
2009.
[5] R. El-Shanawany, M. Higazy, H. Shabana and A. El-Mesady, “Cartesian
product of two symmetric starter vectors of orthogonal double covers”,
AKCE International Journal of Graphs and Combinatorics, Vol. 12, pp. 59-
63, 2015.
[6] H.-D.O.F. Gronau, S. Hartman, M. Grüttmüller, U. Leck and V. Leck, “On
orthogonal double covers of graphs”, Design Codes Cryptography, Vol.
27, pp. 49-91, 2002.
[7] R. El-Shanawany, H.-D.O.F. Gronau, and M. Grüttmüller, “Orthogonal
double covers of
by small graphs”, Discrete Appl. Math, Vol. 138,
pp. 47-63, 2004.
[8] M. Higazy, “A study on the orthogonal double covers of the complete
bipartite graphs”, Master thesis, Menoufia University; 2006.