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.