Geodesic
On the number of additional edges of a minimal vertex 1-extension of a starlike tree
Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 12 (2012) no. 2, pp. 103-113 
M. B. Abrosimov. On the number of additional edges of a minimal vertex 1-extension of a starlike tree. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 12 (2012) no. 2, pp. 103-113. http://geodesic.mathdoc.fr/item/ISU_2012_12_2_a14/
@article{ISU_2012_12_2_a14,
     author = {M. B. Abrosimov},
     title = {On the number of additional edges of a~minimal vertex 1-extension of a~starlike tree},
     journal = {Izvestiya of Saratov University. Mathematics. Mechanics. Informatics},
     pages = {103--113},
     year = {2012},
     volume = {12},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ISU_2012_12_2_a14/}
}
TY  - JOUR
AU  - M. B. Abrosimov
TI  - On the number of additional edges of a minimal vertex 1-extension of a starlike tree
JO  - Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
PY  - 2012
SP  - 103
EP  - 113
VL  - 12
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/ISU_2012_12_2_a14/
LA  - ru
ID  - ISU_2012_12_2_a14
ER  - 
%0 Journal Article
%A M. B. Abrosimov
%T On the number of additional edges of a minimal vertex 1-extension of a starlike tree
%J Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
%D 2012
%P 103-113
%V 12
%N 2
%U http://geodesic.mathdoc.fr/item/ISU_2012_12_2_a14/
%G ru
%F ISU_2012_12_2_a14

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-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 1-extension of the graph $G$ if $G^*$ has $n+1$ nodes and there is no 1-vertex extension with $n+1$ nodes of $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 and upper bounds of the edge number of a minimal vertex 1-extension of a starlike tree and present trees on which these bounds are 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., “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

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

[4] Harary F., Khurum M., “One node fault tolerance for caterpillars and starlike trees”, Intern. 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] Abrosimov M. B., Komarov D. D., Minimalnye vershinnye rasshireniya sverkhstroinykh derevev s malym chislom vershin, Dep. v VINITI 18.10.2010, No 590-V2010, Sarat. gos. un-t, Saratov, 2010, 38 pp.

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

[9] Abrosimov M. B., “O nizhnei otsenke chisla reber minimalnogo rebernogo 1-rasshireniya sverkhstroinogo dereva”, Izv. Sarat. un-ta. Nov. ser. Ser. Matematika. Mekhanika. Informatika, 11:3, ch. 2 (2011), 111–117

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

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