RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika. Supplement // Archive

Prikl. Diskr. Mat. Suppl., 2016 Issue 9, Pages 101–102 (Mi pdma289)

Applied Theory of Automata and Graphs

Refinement of lower bounds for the number of additional arcs in a minimal vertex $1$-extension of oriented path

M. B. Abrosimov, O. V. Modenova

Saratov State University, Saratov

Abstract: Previously known result states that the minimal vertex $1$-extension of any nonhamiltonian path orientation with the number of vertices more than 4 contains at least 4 additional arcs. In this paper, this bound is significantly refined, and upper bound for the number of additional arcs is given.

Keywords: minimal vertex extension, path orientation, fault-tolerance.

UDC: 519.17

DOI: 10.17223/2226308X/9/39



© Steklov Math. Inst. of RAS, 2024