Geodesic
Minimal edge extensions of some precomplete graphs
Prikladnaâ diskretnaâ matematika, no. 1 (2010), pp. 105-117.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider the minimal edge $k$-extensions of precomplete graphs – graphs in which there is a vertex adjacent to all other vertices. The lemma about the marginal value of $k$ when a precomplete graph can have a minimal edge $k$-extension is proved. The full description of all the minimal edge $k$-extensions of precomplete graphs being joins of a complete graph and an empty graph, a chain or a cycle is given.
Keywords: precomplete graph, minimal edge extension, fault tolerance. 
@article{PDM_2010_1_a7,
     author = {M. B. Abrosimov},
     title = {Minimal edge extensions of some precomplete graphs},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {105--117},
     publisher = {mathdoc},
     number = {1},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2010_1_a7/}
}
TY  - JOUR
AU  - M. B. Abrosimov
TI  - Minimal edge extensions of some precomplete graphs
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2010
SP  - 105
EP  - 117
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2010_1_a7/
LA  - ru
ID  - PDM_2010_1_a7
ER  - 
%0 Journal Article
%A M. B. Abrosimov
%T Minimal edge extensions of some precomplete graphs
%J Prikladnaâ diskretnaâ matematika
%D 2010
%P 105-117
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2010_1_a7/
%G ru
%F PDM_2010_1_a7
M. B. Abrosimov. Minimal edge extensions of some precomplete graphs. Prikladnaâ diskretnaâ matematika, no. 1 (2010), pp. 105-117. http://geodesic.mathdoc.fr/item/PDM_2010_1_a7/

[1] Bogomolov A. M., Salii V. N., Algebraicheskie osnovy teorii diskretnykh sistem, Nauka, M., 1997 | MR | Zbl

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

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

[4] Harary F., Hayes J. P., “Node fault tolerance in graphs”, Networks, 27 (1996), 19–23 | 3.0.CO;2-H class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[5] Abrosimov M. B., “O vychislitelnoi slozhnosti rasshirenii grafov”, Prikladnaya diskretnaya matematika, 2009, prilozhenie No 1, 94–95

[6] Abrosimov M. B., “Minimalnye $k$-rasshireniya predpolnykh grafov”, Izv. vuzov. Matematika, 2003, no. 6(493), 3–11 | MR | Zbl