HomeIssuesOn the one edge algorithm for the orthogonal double covers

On the one edge algorithm for the orthogonal double covers | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2019. № 45. DOI: 10.17223/20710410/45/8

The existing problem of the orthogonal double covers of the graphs is well-known in the theory of combinatorial designs. In this paper, a new technique called the one edge algorithm for constructing the orthogonal double covers of the complete bipartite graphs by copies of a graph is introduced. The advantage of this algorithm is that it is accessible to discrete mathematicians not intimately familiar with the theory of the orthogonal double covers.
Download file
Counter downloads: 174
  • Title On the one edge algorithm for the orthogonal double covers
  • Headline On the one edge algorithm for the orthogonal double covers
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 45
  • Date:
  • DOI 10.17223/20710410/45/8
Keywords
graph decomposition, symmetric starter, orthogonal double covers, разложение графа, ортогональные двойные покрытия, ортогональные двойные покрытия
Authors
References
Demetrovics J., Furedi Z., and Katona G. O. H. Minimum matrix representations of closure operations. Discrete Appl. Math., 1985, no. 11, pp. 115-128
Demetrovics J. and Katona G. O. H. External combinatorial problems in relational database. Fundamentals of Combinatorics of Computation Theory, Berlin, Springer, 1981, pp. 110-119
Alspach B., Heinrich K., and Liu G. Orthogonal factorizations of graphs.Contemporary Design Theory, J. H. Dinitz and D. R. Stinson, eds., ch. 2, N.Y., Wiley, 1992
Heinrich K. Graph decompositions and designs. CRC Handbook of Combinatorial Designs, C. J. Colbourn and J. H. Dinitz, eds., ch. IV.22, Boca Raton, CRC Press, 1996
Scapellato R., El-Shanawany R., and Higazy M. Orthogonal double covers of Cayley graphs. Discrete Appl. Math., 2009, vol. 157, pp. 3111-3118
El-Shanawany R., Higazy M., Shabana H., and El-Mesady A. Cartesian product of two symmetric starter vectors of orthogonal double covers. AKCE Intern. J. Graphs and Combinatorics, 2015, no. 12, pp. 59-63
Gronau H.-D. O. F., Hartman S., Griittmuller M., et al. On orthogonal double covers of graphs. Design Codes Cryptography, 2002, vol. 27, pp. 49-91
El-Shanawany R., Gronau H.-D. O. F., and Gruittmuiller M. Orthogonal double covers of Kn,n by small graphs. Discrete Appl. Math., 2004, vol. 138, pp. 47-63
El-Serafi S., El-Shanawany R., and Shabana H. Orthogonal double cover ofcomplete bipartite graph by disjoint union of complete bipartite graphs. Ain Shams Engineering J., 2015, no. 6, pp. 657-660
Sampathkumar R. and Srinivasan S. Cyclic orthogonal double covers of 4-regular circulant graphs. Discr. Math., 2011, vol. 311, pp. 2417-2422
El-Shanawany R., Higazy M., and El-Mesady A. On cartesian products of orthogonal double covers. Intern. J. Math. and Math. Sci., 2013, vol. 2013, Article ID 265136, 4 p
Froncek D. Orthogonal double covers of complete graphs by lobsters of diameter 4. Congr. Numer., 2005, vol. 177, pp. 25-32
On the one edge algorithm for the orthogonal double covers | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2019. № 45. DOI: 10.17223/20710410/45/8
On the one edge algorithm for the orthogonal double covers | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2019. № 45. DOI: 10.17223/20710410/45/8
Download full-text version
Counter downloads: 385