RUS  ENG
Full version
JOURNALS // Izvestiya of Saratov University. Mathematics. Mechanics. Informatics // Archive

Izv. Saratov Univ. Math. Mech. Inform., 2010 Volume 10, Issue 1, Pages 83–88 (Mi isu14)

Computer science

On directed acyclic exact extensions

M. B. Abrosimov, A. A. Dolgov

Saratov State University, Chair of Theoretical Basis of Computer Security and Cryptography

Abstract: Exact extensions of undirected graphs are well studied, but exact extensions of directed graphs are much less known.We prove that only directed acyclic graph or strongly connected graph can be an exact extension. Furthermore, only transitive tournament can be directed acyclic exact extension.

Key words: directed acyclic graph, transitive tournament, exact extension.

UDC: 519.17

DOI: 10.18500/1816-9791-2010-10-1-83-88



© Steklov Math. Inst. of RAS, 2024