|
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.
Citation:
O. V. Modenova, M. B. Abrosimov, “The upper and lower bounds for the number of additional arcs in a minimal edge $1$-extension of oriented cycle”, Prikl. Diskr. Mat. Suppl., 2022, no. 15, 112–116
Linking options:
https://www.mathnet.ru/eng/pdma592 https://www.mathnet.ru/eng/pdma/y2022/i15/p112
|
Statistics & downloads: |
Abstract page: | 74 | Full-text PDF : | 19 | References: | 17 |
|