|
This article is cited in 3 scientific papers (total in 3 papers)
Computer science
On lower bound of edge number of minimal edge 1-extension of 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-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.
Key words:
minimal edge extension, starlike tree, fault tolerance.
Citation:
M. B. Abrosimov, “On lower bound of edge number of minimal edge 1-extension of starlike tree”, Izv. Saratov Univ. Math. Mech. Inform., 11:3(2) (2011), 111–117
Linking options:
https://www.mathnet.ru/eng/isu258 https://www.mathnet.ru/eng/isu/v11/i4/p111
|
|