Applied graph theory

Building edge extensions of star-like trees

D. D. Komarov

Saratov State University, Saratov

Abstract: Minimal edge extension of a graph can be regarded as a model of optimal edge fault tolerant implementation of a system. This paper is about the upper bound of the number of additional edges in a minimal edge $1$-extensions for a special class of graphs – star-like trees. In this paper, a scheme for constructing an edge $1$-extension for any kind of star-like trees is presented.

Keywords: minimal extensions of graphs, star-like tree, fault tolerance.

UDC: 519.17