Applied Graph Theory

Upper bound for the number of additional edges in minimal $1$-edge extensions of starlike trees

D. D. Komarov

Saratov State University, Saratov, Russia

Abstract: Minimal edge extension of graphs can be regarded as a model of optimal edge fault tolerant implementation of a system. This paper is about an upper bound for the number of additional edges in minimal $1$-edge extensions for graphs of a special class – starlike trees. Two schemes for constructing $1$-edge extensions for any kind starlike trees and an algorithm based on these schemes are proposed.

Keywords: graphs, minimal extensions of graphs, fault tolerance, starlike trees.

UDC: 519.17

DOI: 10.17223/20710410/30/9

Bibliographic databases:

•