Let be a connected graph with vertex set , and denote by the distance from to in , for any . The average distance of an -vertex connected graph , denoted by , is defined to be the average of all distances between all pairs of vertices in , i.e., . The problem of finding a spanning tree of minimum average distance is known to be NP-hard, so establishing an upper bound for the minimum average distance among all spanning trees is of particular interest. Mukwembi (J. Graph Theory, 2014) showed that if is a connected graph of order with independence number , where , then has a spanning tree such that . In this paper, we first improve the upper bound to for , and then we find the bound could be further improved when becomes larger, so a better upper bound is established later. In the end, we give a remark to indicate our new upper bound is best possible in the sense of asymptotics (when and are large enough).

生成讲解博客的中文版本

生成AI智能校验的中文版本