Geodesic
On lower bound of edge number of minimal edge 1-extension of starlike tree
Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 11 (2011) no. 3, pp. 111-117 
M. B. Abrosimov. On lower bound of edge number of minimal edge 1-extension of starlike tree. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 11 (2011) no. 3, pp. 111-117. http://geodesic.mathdoc.fr/item/ISU_2011_11_3_a17/
@article{ISU_2011_11_3_a17,
     author = {M. B. Abrosimov},
     title = {On lower bound of edge number of minimal edge 1-extension of starlike tree},
     journal = {Izvestiya of Saratov University. Mathematics. Mechanics. Informatics},
     pages = {111--117},
     year = {2011},
     volume = {11},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ISU_2011_11_3_a17/}
}
TY  - JOUR
AU  - M. B. Abrosimov
TI  - On lower bound of edge number of minimal edge 1-extension of starlike tree
JO  - Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
PY  - 2011
SP  - 111
EP  - 117
VL  - 11
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/ISU_2011_11_3_a17/
LA  - ru
ID  - ISU_2011_11_3_a17
ER  - 
%0 Journal Article
%A M. B. Abrosimov
%T On lower bound of edge number of minimal edge 1-extension of starlike tree
%J Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
%D 2011
%P 111-117
%V 11
%N 3
%U http://geodesic.mathdoc.fr/item/ISU_2011_11_3_a17/
%G ru
%F ISU_2011_11_3_a17

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 1-edge extension if for each edge $e$ of $G^*$ the subgraph $G^*-e$ contains graph $G$ up to isomorphism. Graph $G^*$ is minimal 1-edge extension of graph $G$ if $G^*$ has $n$ nodes and there is no 1-edge extension with $n$ nodes of graph $G$ having fewer edges than $G$. A tree is called starlike if it has exactly one node of degree greater than two. We give a lower bound of edge number of minimal edge 1-extension of starlike tree and provide family on which this bound is achieved.

[1] Hayes J. P., “A graph model for fault-tolerant computing system”, IEEE Trans. Comput., 25: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] Harary F., Khurum M., “One node fault tolerance for caterpillars and starlike trees”, Internet J. Comput. Math., 56 (1995), 135–143 | DOI | Zbl

[5] Kabanov M. A., “Ob otkazoustoichivykh realizatsiyakh grafov”, Teoreticheskie zadachi informatiki i ee prilozhenii, 1, Saratov, 1997, 50–58 | MR

[6] Abrosimov M. B., “Minimalnye rasshireniya grafov”, Novye informatsionnye tekhnologii v issledovanii diskretnykh struktur, Tomsk, 2000, 59–64

[7] M. B. Abrosimov, D. D. Komarov, Minimalnye rebernye rasshireniya sverkhstroinykh derevev s malym chislom vershin, Dep. v VINITI 18.10.2010, No 589-V2010, Saratov. gos. un-t, Saratov, 2010, 27 pp.

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

[9] Bogomolov A. M., Salii V. N., Algebraicheskie osnovy teorii diskretnykh sistem, M., 1997, 368 pp. | MR | Zbl

[10] Sloane N. J. A., Plouffe S., The Encyclopedia of Integer Sequences, San Diego, 1995, 587 pp. | MR

[11] Abrosimov M. B., “Minimalnye rasshireniya neorientirovannykh zvezd”, Teoreticheskie problemy informatiki i ee prilozhenii, 7, Saratov, 2006, 3–5