Cite this article as:

Abrosimov M. B. On Directed Acyclic Exact Extensions. Izv. Saratov Univ. (N. S.), Ser. Math. Mech. Inform., 2010, vol. 10, iss. 1, pp. 83-88. DOI: https://doi.org/10.18500/1816-9791-2010-10-1-83-88

Language: 
Russian
Heading: 
Computer Sciences
UDC: 
519.17

On Directed Acyclic Exact Extensions

Authors: 
Abrosimov Mikhail Borisovich, Moscow Aviation Institute (State University of Aerospace Technologies), Russia, 125993, Moscow, GSP-3, A-80, Volokolamskoe Shosse, 4, azemskov1975@mail.ru, , mic@rambler.ru
Abstract: 

Exact extensions of undirected graphs are well studied, but exact extensions of directed graphs are much less known.We prove that only directe dacyclicgraphor strongly connected graph can be an exact extension. Further more, only transitive tournament can be directed acyclic exact extension.

Key words: 
directed acyclic graph, transitive tournament, exact extension
DOI: 
https://doi.org/10.18500/1816-9791-2010-10-1-83-88
References

1. Harary F., Hayes J.P. Node fault tolerance in graphs // Networks. 1996. V. 27. P. 19–23.

2. Абросимов М.Б. Минимальные расширения дополнений графов // Теоретические задачи информатики и ее приложений. Саратов: Изд-во Сарат. ун-та, 2001. Вып. 4. С. 11–19.
3. Абросимов М.Б., Долгов А.А. Точные расширения некоторых турниров // Вестн. Томск. гос. ун-та. Приложение. 2007. № 23. С. 211–216.
4. Богомолов А.М., Салий В.Н. Алгебраические основы теории дискретных систем. М.: Наука, 1997.
 

Full text:
download
60