Refinement of lower bounds for the number of additional arcs in a minimal vertex 1-ex-tension of oriented path | Applied Discrete Mathematics. Supplement. 2016. № 9.

Refinement of lower bounds for the number of additional arcs in a minimal vertex 1-ex-tension of oriented path

Previously known result states that the minimal vertex 1-extension of any nonhamiltonian path orientation with the number of vertices more than 4 contains at least 4 additional arcs. In this paper, this bound is significantly refined, and upper bound for the number of additional arcs is given.

Download file

Counter downloads: 653

Keywords

минимальное вершинное 1-расширение, ориентация цепи, отказоустойчивость, minimal vertex extension, path orientation, fault-tolerance

Authors

Name	Organization	E-mail
Abrosimov M. B.	Saratov State University	mic@rambler.ru
Modenova O. V.	Saratov State University	oginiel@rambler.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.

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

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

Абросимов М. Б., Моденова О. В. Характеризация орграфов с малым числом дополнительных дуг минимального вершинного 1-расширения // Изв. Сарат. ун-та. Нов. сер. 2013. Т. 13. Сер. Математика. Механика. Информатика. Вып. 2. Ч.2. С. 3-9.

Абросимов М. Б., Моденова О. В. Характеризация орграфов с тремя дополнительными дугами в минимальном вершинном 1-расширении // Прикладная дискретная математика. 2013. №3. С. 68-75.