ГлавнаяАрхивОб одном алгоритме построения ортогонального двойного покрытия

Об одном алгоритме построения ортогонального двойного покрытия | Прикладная дискретная математика. 2019. № 45. DOI: 10.17223/20710410/45/8

Проблема ортогональных двойных покрытий графов хорошо известна в теории комбинаторных конструкций. В работе предлагается новая методика, называемая односторонним алгоритмом для построения ортогональных двойных покрытий полных двудольных графов посредством копий графа. Преимуществом алгоритма является простота, что делает его доступным для математиков, не очень хорошо знакомых с теорией ортогональных двойных покрытий.
  • Title Об одном алгоритме построения ортогонального двойного покрытия
  • Headline Об одном алгоритме построения ортогонального двойного покрытия
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 45
  • Date:
  • DOI 10.17223/20710410/45/8
Ключевые слова
graph decomposition, symmetric starter, orthogonal double covers, разложение графа, ортогональные двойные покрытия, ортогональные двойные покрытия
Авторы
Ссылки
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
Об одном алгоритме построения ортогонального двойного покрытия | Прикладная дискретная математика. 2019. № 45. DOI: 10.17223/20710410/45/8
Об одном алгоритме построения ортогонального двойного покрытия | Прикладная дискретная математика. 2019. № 45. DOI: 10.17223/20710410/45/8