2022/06/14 by Gyan Ranjan, Ranjan, Gyan, Nishant Saurabh +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #Distributed #FOS: Computer and information sciences #Graph theory and applications #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2206.07104
openalex publication_date 2022/06/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce the concept of Most, and Least, Compact Spanning Trees - denoted respectively by T^*(G) and T^#(G) - of a simple, connected, undirected and unweighted graph G(V, E, W). For a spanning tree T(G) ∈ T(G) to be considered T^*(G), where T(G) represents the set of all the spanning trees of the graph G, it must have the least average inter-vertex pair (shortest path) distances from amongst the members of the set T(G). Similarly, for it to be considered T^#(G), it must have the highest average inter-vertex pair (shortest path) distances. In this work, we present an iteratively greedy rank-and-regress method that produces at least one T^*(G) or T^#(G) by eliminating one extremal edge per iteration. The rank function for performing the elimination is based on the elements of the matrix of relative forest accessibilities of a graph and the related forest distance. We provide empirical evidence in support of our methodology using some standard graph families: complete graphs, the Erdős-Renyi random graphs and the Barabási-Albert scale-free graphs; and discuss computational complexity of the underlying methods which incur polynomial time costs.