Some results about the inset edge and average distance of trees.

An added edge to a graph is called an inset edge. Predicting k inset edges, which minimize the average distance of a graph, is known to be NP-Hard. However, when k = 1 , the complexity of the problem is polynomial. In this paper, some tools for a precise analysis of the effect of inset edges on the tree's average distance are established. Using the tools, one can avoid using the distance matrix for better performance of algorithms. Here, some applications of the tools and a tight bound for the change of average distance when an inset edge is added to a tree are presented. [ABSTRACT FROM AUTHOR]