The upper and lower bounds for the number of additional arcs in a minimal edge 1-exten-sion of oriented cycle | Applied Discrete Mathematics. Supplement. 2022. № 15. DOI: 10.17223/2226308X/15/27

The upper and lower bounds for the number of additional arcs in a minimal edge 1-exten-sion of oriented cycle

A k-edge extension of a graph G with n vertices is minimal if it has n vertices and contains the minimum number of edges or arcs among all k-edge extensions of G with n vertices. Minimal edge 1-extensions of cycles are well studied. In this paper, we consider minimal edge 1-extensions of cycle orientations. We study the upper and lower bounds for the number of additional arcs ec(Cn) of a minimal edge 1-extension of the oriented cycle Cn. The main result is an estimate for the number of additional arcs: dn=2e 6 ec(Cn) 6 n. Examples of cycle orientations on which the upper and lower bounds are achieved are given.

Download file

Counter downloads: 14

Keywords

minimal edge extension, cycle orientation, fault-tolerance

Authors

Name	Organization	E-mail
Modenova Olga V.	Saratov National Research State University named after N. G. Chernyshevsky	oginiel@rambler.ru
Abrosimov Mihail B.	Saratov National Research State University named after N. G. Chernyshevsky	mic@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.

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

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

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