Some results about the inset edge and average distance of trees (Q2104937)

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 except when \(k = 1\), where the complexity of the problem is polynomial. This article discusses some tools for a precise analysis of the effect of inseting edges on the tree's average distance. The tools help to avoid the use of distance matrices for a better performance of algorithms. 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.