Geodesic
The upper and lower bounds for the number of additional arcs in a minimal edge $1$-extension of oriented cycle
Prikladnaya Diskretnaya Matematika. Supplement, no. 15 (2022), pp. 112-116 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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, fault-tolerance.
Mots-clés : cycle orientation 
@article{PDMA_2022_15_a26,
     author = {O. V. Modenova and M. B. Abrosimov},
     title = {The upper and lower bounds for the number of additional arcs in a minimal edge $1$-extension of oriented cycle},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {112--116},
     year = {2022},
     number = {15},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2022_15_a26/}
}
TY  - JOUR
AU  - O. V. Modenova
AU  - M. B. Abrosimov
TI  - The upper and lower bounds for the number of additional arcs in a minimal edge $1$-extension of oriented cycle
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2022
SP  - 112
EP  - 116
IS  - 15
UR  - http://geodesic.mathdoc.fr/item/PDMA_2022_15_a26/
LA  - ru
ID  - PDMA_2022_15_a26
ER  - 
%0 Journal Article
%A O. V. Modenova
%A M. B. Abrosimov
%T The upper and lower bounds for the number of additional arcs in a minimal edge $1$-extension of oriented cycle
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2022
%P 112-116
%N 15
%U http://geodesic.mathdoc.fr/item/PDMA_2022_15_a26/
%G ru
%F PDMA_2022_15_a26
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. Prikladnaya Diskretnaya Matematika. Supplement, no. 15 (2022), pp. 112-116. http://geodesic.mathdoc.fr/item/PDMA_2022_15_a26/

[1] Hayes J. P., “A graph model for fault-tolerant computing system”, IEEE Trans. Comput., C25:9 (1976), 875–884 | DOI | MR | Zbl

[2] Harary F. and Hayes J. P., “Edge fault tolerance in graphs”, Networks, 23 (1993), 135–142 | DOI | MR | Zbl

[3] Abrosimov M. B., Grafovye modeli otkazoustoichivosti, Izd-vo Sarat. un-ta, Saratov, 2012, 192 pp.

[4] Abrosimov M. B., “O slozhnosti nekotorykh zadach, svyazannykh s rasshireniyami grafov”, Matem. zametki, 88:5 (2010), 643–650 | MR | Zbl