About minimal 1-edge extension of hy-percube
A hypercube Qn is a regular 2n-vertex graph of order n, which is the Cartesian product of n complete 2-vertex graphs K2. For any integer n > 1, we define a graph Qn by connecting each vertex v in Qn with one which is most far from v. It is shown that Qn is the minimal 1-edge extension of the hypercube Qn. The computational experiment shows that for each n ^ 4 this extension is unique up to isomorphism.
Download file
Counter downloads: 187
Keywords
minimal 1-edge extension, edge fault tolerance, hypercube, graph, минимальное рёберное 1-расширение, рёберная отказоустойчивость, гиперкуб, графAuthors
| Name | Organization | |
| Lobov A. A. | Saratov National Research University | aisanekai@mail.ru |
| Abrosimov M. B. | Saratov National Research University | mic@rambler.ru |
References
Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Матем. заметки. 2010. №5(88). С. 643-650.
Meringer M. Fast generation of regular graphs and construction of cages // J. Graph Theory. 1999. V. 30. P. 137-146.
Harary F., Hayes J. P., and Wu H.-J. A survey of the theory of hypercube graphs // Computers & Math. Appl. 1988. V. 15. P. 277-289.
Padua D. A. Encyclopedia of Parallel Computing. N.Y.: Springer, 2011.
Абросимов М. Б. Графовые модели отказоустойчивости. Саратов: Изд-во Сарат. ун-та, 2012. 192 с.
Hayes J. P. A graph model for fault-tolerant computing system // IEEE Trans. Comput. 1976. V.C.25. No. 9. P. 875-884.
Harary F. and Hayes J. P. Edge fault tolerance in graphs // Networks. 1993. V. 23. P. 135-142.
