On a counterexample to a minimal vertex $1$-extension of starlike trees
Prikladnaya Diskretnaya Matematika. Supplement, no. 5 (2012), pp. 83-84
Citer cet article
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 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 extension of a starlike tree and present trees for which these bounds are achieved.
[1] Abrosimov M. B., “Minimalnye rasshireniya grafov”, Novye informatsionnye tekhnologii v issledovanii diskretnykh struktur, Tomsk, 2000, 59–64
[2] Harary F., Khurum M., “One node fault tolerance for caterpillars and starlike trees”, Internet J. Comput. Math., 56 (1995), 135–143 | DOI | Zbl
[3] Abrosimov M. B., Komarov D. D., Minimalnye vershinnye rasshireniya sverkhstroinykh derevev s malym chislom vershin, Dep. v VINITI 18.10.2010, No 7590-V, SGU, Saratov, 2010, 38 pp.