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-?.


Language: 
Russian
Heading: 
UDC: 
519.17

On Directed Acyclic Exact Extensions

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.

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: