On the number of optimal 1-hamilto-nian graphs with the number of vertices up to 26 and 28 | Applied Discrete Mathematics. Supplement. 2016. № 9.

On the number of optimal 1-hamilto-nian graphs with the number of vertices up to 26 and 28

A graph is called 1-vertex-hamiltonian (1-edge-hamiltonian) one, if it becomes Hamilto-nian after deleting any its vertex (edge). 1-vertex-hamiltonian (1-edge-hamilton) graph is optimal if it has the minimum number of edges among all 1-vertex-hamiltonian (1-edge-hamiltonian) graphs with the same number of vertices. In the paper, the previous data on the number of optimal 1-vertex- and 1-edge-hamiltonian graphs with the number of vertices up to 26 are verified, and new data for 28-vertex graphs are given.

Download file

Counter downloads: 605

Keywords

оптимальный 1-гамильтонов граф, минимальное 1-расширение цикла, отказоустойчивость, optimal 1-hamiltonian (graph, minimal 1-extension of cycle, fault-tolerance

Authors

Name	Organization	E-mail
Abrosimov M.B.	Saratov State University	mic@rambler.ru
Suhov S. A.	Saratov State University	serega_suhov@mail.ru

Всего: 2

References

Hayes J. P. A graph model for fault-tolerant computing system // IEEE Trans. Comput. 1976. V.C25. No. 9. P. 875-884.

Harary F. and Hayes J. P. Edge fault tolerance in graphs // Networks. 1993. V. 23. P. 135-142.

Harary F. and Hayes J. P. Node fault tolerance in graphs // Networks. 1996. V. 27. P. 19-23.

Mukhopadhyaya K. and Sinha B. P. Hamiltonian graphs with minimum number of edges for fault-tolerant topologies // Inform. Process. Lett. 1992. V. 44. P. 95-99.

Hsu L. H. and Lin C. K. Graph Theory and Interconnection Networks. CRC Press, 2009.

Абросимов М. Б. О неизоморфных оптимальных 1-отказоустойчивых реализациях некоторых графов // Теоретические проблемы информатики и её приложений. Саратов: СГУ, 2000. Вып. 3. С. 3-10.

Абросимов М. Б. О неизоморфных минимальных реберных 1-расширениях графов // Теоретические проблемы информатики и её приложений. Саратов: СГУ, 2004. Вып. 6. С. 3-9.

Абросимов М. Б. Графовые модели отказоустойчивости. Саратов: Изд-во Сарат. ун-та, 2012.

Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Матем. заметки. 2010. №5(88). С. 643-650.

Абросимов М. Б. Минимальные вершинные расширения циклов с числом вершин не более одиннадцати. Саратов: СГУ, 2001. 17с. Деп. в ВИНИТИ 14.08.2001, №1869-В2001.

Абросимов М. Б., Кузнецов Н. А. О количестве минимальных вершинных и рёберных 1-раотирений циклов с числом вершин до 17 // Прикладная дискретная математика. Приложение. 2012. №5. С. 84-86.

Бринкман Г., Абросимов М. Б. О количестве минимальных раотирений циклов с числом вершин до 26 и 28 // Дискретная математика, теория графов и их приложения: Тез. докл. Междунар. науч. конф. Минск, 11-14 ноября 2013 г. Мн.: Институт математики НАН Беларуси, 2013. С. 7-9.

Brinkmann G. Fast generation of cubic graphs // J. Graph Theory. 1996. V. 23. P. 139-140.

Brinkmann G., Goedgebeur J., and McKay B. D. Generation of cubic graphs // Discr. Math. Theor. Comp. Sci. 2011. V. 13(2). P.69-80.

Grund R. Konstruktion schlichter Graphen mit gegebener Gradpartition // Bayreuther Mathematische Schriften. 1993. B.44. S. 73-104.

Сухов С. А. DSR Generator. Свид. о гос. регистрации программы для ЭВМ №2016610073. Зарегистрирована в Реестре программ для ЭВМ 11 января 2016 г.