Applied Theory of Coding, Automata and Graphs

Number estimation for additional arcs in a minimal $1$-vertex extension of tournament

M. B. Abrosimov, O. V. Modenova

Saratov State University, Saratov

Abstract: We obtain lower and upper bounds for the number of additional arcs in minimal vertex $1$-extension of arbitrary tournament. It is shown that the estimates are sharp. We describe tournaments, for which estimates are attained.

Keywords: tournament, minimal vertex extension, fault-tolerance.

UDC: 519.17

DOI: 10.17223/2226308X/8/42