Graph G* = (V*, α∗) is said to be an exactk-extension of a graph G = (V, α) if every graph obtained by removing any k vertexes from G* and graph G are isomorphic. Wepresent some basic conditions that directed graph must meet to be an exact k-extension. We then study the problem of constructingexact k-extension of tournaments. Presented four families of tournaments with their exact extensions. We show some experimentaldata collected during study exact extensions of tournaments.
Download file
Counter downloads: 94
- Title FAMILIES OF TOURNAMENTS EXTENSIONS
- Headline FAMILIES OF TOURNAMENTS EXTENSIONS
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 1(1)
- Date:
- DOI
Keywords
точное расширение , минимальное расширение , турнир , орграф , оптимальная отказоустойчивая реализация , точная отказоустойчивая реализация Authors
References
Абросимов М.Б. Некоторые вопросы о минимальных расширениях графов // Изв. Саратовского университета. 2006. №6. С. 86-91.
Абросимов М.Б., Долгов А.А. Точные расширения некоторых турниров // Вестник ТГУ. Приложение. 2007. № 23. С. 211-216.
Абросимов М.Б. Минимальные расширения транзитивных турниров // Вестник ТГУ. Приложение. 2006. № 17. С. 187 -190.
Harary F., Hayes J. P. Node fault tolerance in graphs //Networks. 1996. V.27.P. 19-23.
Абросимов М.Б. Минимальные расширения дополнений графов // Теоретические задачи информатики и ее приложений. Саратов: СГУ, 2001. Вып. 4. С. 11 - 19.
Hayes J.P. A graph model for fault-tolerant computing system // IEEE Trans. Comput. 1976. V. C-25. No. 9. P.875 - 884.
Богомолов A.M., Салий В.Н. Алгебраические основы теории дискретных систем. М.: Наука, 1997.
FAMILIES OF TOURNAMENTS EXTENSIONS | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2008. № 1(1).
Download full-text version
Download fileCounter downloads: 671