Minimal edge extension of graphs can be regarded as a model of optimal edge fault tolerant implementation of a system. This paper is about an upper bound for the number of additional edges in minimal 1-edge extensions for graphs of a special class - starlike trees. Two schemes for constructing 1-edge extensions for any kind starlike trees and an algorithm based on these schemes are proposed.
Download file
Counter downloads: 294
- Title Upper bound for the number of additional edges in minimal 1-edge extensions of starlike trees
- Headline Upper bound for the number of additional edges in minimal 1-edge extensions of starlike trees
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 4(30)
- Date:
- DOI
Keywords
графы, минимальные расширения графов, сверхстройное дерево, отказоустойчивость, graphs, minimal extensions of graphs, fault tolerance, starlike treesAuthors
References
Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Матем. заметки. 2010. Т. 88. №5. С. 643-650.
Абросимов М. Б. О нижней оценке числа ребер минимального реберного 1-расширения сверхстройного дерева // Изв. Сарат. ун-та. Нов. сер. Математика. Механика. Информатика. 2011. Т. 11. Вып. 3. Ч.2. С. 111-117.
Harary F. and Hayes J. P. Edge fault tolerance in graphs // Networks. 1993. No. 23. P. 135-142.
Абросимов М. Б. Графовые модели отказоустойчивости. Саратов: Изд-во Сарат. ун-та, 2012. 192 с.
Абросимов М. Б., Комаров Д. Д. Минимальные реберные расширения сверхстройных деревьев с малым числом вершин. Саратов, 2010. 27с. Деп. в ВИНИТИ 18.10.2010 №589-В2010.
Upper bound for the number of additional edges in minimal 1-edge extensions of starlike trees | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2015. № 4(30).
Download full-text version
Counter downloads: 775