Geodesic
On the number of minimal vertex and edge $1$-extensions of cycles
Prikladnaya Diskretnaya Matematika. Supplement, no. 5 (2012), pp. 84-86 
M. B. Abrosimov; N. A. Kuznetsov. On the number of minimal vertex and edge $1$-extensions of cycles. Prikladnaya Diskretnaya Matematika. Supplement, no. 5 (2012), pp. 84-86. http://geodesic.mathdoc.fr/item/PDMA_2012_5_a42/
@article{PDMA_2012_5_a42,
     author = {M. B. Abrosimov and N. A. Kuznetsov},
     title = {On the number of minimal vertex and edge $1$-extensions of cycles},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {84--86},
     year = {2012},
     number = {5},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2012_5_a42/}
}
TY  - JOUR
AU  - M. B. Abrosimov
AU  - N. A. Kuznetsov
TI  - On the number of minimal vertex and edge $1$-extensions of cycles
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2012
SP  - 84
EP  - 86
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/PDMA_2012_5_a42/
LA  - ru
ID  - PDMA_2012_5_a42
ER  - 
%0 Journal Article
%A M. B. Abrosimov
%A N. A. Kuznetsov
%T On the number of minimal vertex and edge $1$-extensions of cycles
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2012
%P 84-86
%N 5
%U http://geodesic.mathdoc.fr/item/PDMA_2012_5_a42/
%G ru
%F PDMA_2012_5_a42

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

For a given graph $G$ with $n$ nodes, we say that graph $G^*$ is its vertex extension if for each vertex $v$ of $G^*$ the subgraph $G^*-v$ contains graph $G$ up to isomorphism. A graph $G^*$ is a minimal vertex extension of the graph $G$ if $G^*$ has $n+1$ nodes and there is no vertex extension with $n+1$ nodes of $G$ having fewer edges than $G^*$. A graph $G^*$ is edge extension of graph $G$ with $n$ nodes if every graph obtained by removing any edge from $G^*$ contains $G$. Edge extension of graph $G$ with $n$ vertices is called minimal if among all edge extensions of graph $G$ with $n$ vertices it has the minimum possible number of edges. We present the results of computational experiment in which all minimal vertex and edge extensions of cycles up to 17 vertices were found.

[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., Hayes J. P., “Edge fault tolerance in graphs”, Networks, 23 (1993), 135–142 | DOI | MR | Zbl

[3] 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

[4] Mukhopadhyaya K., Sinha B. P., “Hamiltonian graphs with minimum number of edges for fault-tolerant topologies”, Inform. Process. Lett., 44 (1992), 95–99 | DOI | MR | Zbl

[5] Hsu L. H., Lin C. K., Graph Theory and Interconnection Networks, CRC Press, 2009 | MR | Zbl

[6] Abrosimov M. B., “O neizomorfnykh optimalnykh 1-otkazoustoichivykh realizatsiyakh nekotorykh grafov”, Teoreticheskie problemy informatiki i eë prilozhenii, 3, SGU, Saratov, 2000, 3–10

[7] Abrosimov M. B., “O neizomorfnykh minimalnykh rebernykh 1-rasshireniyakh grafov”, Teoreticheskie problemy informatiki i eë prilozhenii, 6, SGU, Saratov, 2004, 3–9

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

[9] Abrosimov M. B., Minimalnye vershinnye rasshireniya tsiklov s chislom vershin ne bolee odinnadtsati, Dep. v VINITI 14.08.2001, No 1869-V, SGU, Saratov, 2001, 17 pp.