About the lower bounds for the number of additional arcs in a minimal vertex 1-extension of oriented path
A graph G* with n + k vertices is vertex k-extension of a graph G if every graph obtained by removing any k vertices from G* contains G; it is called minimal vertex k-extension of G if it has the least number of arcs among all vertex k-extensions of graph G with n + k vertices. A lower bound for the number of additional arcs in minimal vertex 1-extension of an oriented path is given.
Download file
Counter downloads: 265
Keywords
граф, минимальное вершинное расширение, отказоустойчивость, graph, minimal vertex extension, fault toleranceAuthors
| Name | Organization | |
| Abrosimov M. B | Saratov State University | mic@rambler.ru |
| Modenova O. V. | Saratov State University | oginiel@rambler.ru |
References
Hayes J. P. A graph model for fault-tolerant computing system // IEEE Trans. Comput. 1976. V.C-25. No. 9. P. 875-884.
Абросимов М. Б. Графовые модели отказоустойчивости. Саратов: Изд-во Сарат. ун-та, 2012. 192 с.
Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Матем. заметки. 2010. Т. 88. Вып. 5. С. 643-650.
Абросимов М. Б. Минимальные вершинные расширения направленных звезд // Дискретная математика. 2011. №23:2. С. 93-102.
