Applied Theory of Coding, Automata and Graphs

Upper and lower bounds of the number of additional arcs in a minimal edge $1$-extension of oriented path

M. B. Abrosimov^a, O. V. Modenova<sup>b

a</sup> Saratov State University, Saratov
^b Saratov

Abstract: The following upper and lower bounds of the number of additional arcs $ec(P_n)$ in a minimal edge $1$-extension of an oriented path $P_n$ are obtained: 1) for $P_n$ which has ends of different types and is not isomorphic to Hamiltonian path or to orientation consisting of alternating sources and sinks, $\lceil n/6\rceil+1\leq ec(P_n)\leq n+1$; 2) for $P_n$ with ends of equal types, $\lceil n/4\rceil+1\leq ec(P_n)\leq n+1$.

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

UDC: 519.17

DOI: 10.17223/2226308X/10/52