RUS  ENG
Full version
JOURNALS // Izvestiya of Saratov University. Mathematics. Mechanics. Informatics // Archive

Izv. Saratov Univ. Math. Mech. Inform., 2012 Volume 12, Issue 2, Pages 103–113 (Mi isu303)

This article is cited in 1 paper

Computer science

On the number of additional edges of a minimal vertex 1-extension of a starlike tree

M. B. Abrosimov

Saratov State University, Chair of Theoretical Foundations of Computer Security and Cryptography

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

Key words: minimal vertex extension, starlike tree, fault tolerance.

UDC: 519.17

DOI: 10.18500/1816-9791-2012-12-2-103-113



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024