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

Prikl. Diskr. Mat. Suppl., 2022 Issue 15, Pages 112–116 (Mi pdma592)

Applied Theory of Coding and Graphs

The upper and lower bounds for the number of additional arcs in a minimal edge $1$-extension of oriented cycle

O. V. Modenova, M. B. Abrosimov

Saratov State University

Abstract: A $k$-edge extension of a graph $G$ with $n$ vertices is minimal if it has $n$ vertices and contains the minimum number of edges or arcs among all $k$-edge extensions of $G$ with $n$ vertices. Minimal edge $1$-extensions of cycles are well studied. In this paper, we consider minimal edge $1$-extensions of cycle orientations. We study the upper and lower bounds for the number of additional arcs $\text{ec}(C_n)$ of a minimal edge $1$-extension of the oriented cycle $C_n$. The main result is an estimate for the number of additional arcs: $\left\lceil {n}/{2} \right\rceil \leq \text{ec}(C_n) \leq n$. Examples of cycle orientations on which the upper and lower bounds are achieved are given.

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

UDC: 519.17

DOI: 10.17223/2226308X/15/27



© Steklov Math. Inst. of RAS, 2024