Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)

For citation:

Abrosimov M. B., Dolgov A. A. On Directed Acyclic Exact Extensions. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2010, vol. 10, iss. 1, pp. 83-88. DOI: 10.18500/1816-9791-2010-10-1-83-88

This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online: 
Full text:
(downloads: 178)

On Directed Acyclic Exact Extensions

Abrosimov Mikhail Borisovich, Saratov State University
Dolgov Aleksandr Alekseevich, Saratov State University

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.

  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.