This article is cited in 2 papers

Applied graph theory

On a counterexample to a minimal vertex $1$-extension of starlike trees

M. B. Abrosimov, D. D. Komarov

Saratov State University, Saratov

Abstract: 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.

UDC: 519.17