Exactly k MSTs How Many Vertices Suffice

Abstract

Minimum spanning trees have many practical, combinatorial, and algorithmic applications. newlineCounting variants of combinatorial problems are often as significant as the combinatorial newlineproblems themselves. In the context of spanning trees and minimum spanning newlinetrees, a lot of work has been done on enumeration and counting, in addition to algorithms newlinefor computing such trees. For instance, it has been shown that the number of spanning newlinetrees of the complete graph Kn is nnand#8722;2. In this thesis, we aim to generalize and extend this newlineresult to an arbitrary number of MSTs in edge-weighted complete graphs. More specifically, newlinewe aim to address the question of whether for a given pair of integers (n, k) with newline1 and#8804; k and#8804; n(nand#8722;2), there exists a weighted complete undirected graph Kn, such that it has newlineexactly k minimum spanning trees, or not. Some methods are discussed here for different newlinescenarios, which can help us in deducing the answer. We have set up a framework to look newlineat various aspects of this problem from different angles. We have devised various ideas to newlinetackle this problem and obtained partial results. newlineIn this work, the problem is to find a weighted complete graph of n vertices (Kn), newlinewith exactly k minimum spanning trees (MSTs, in short) while minimizing n. While newlinefinding a graph with k MSTs is easy, finding such a graph with the minimum number of newlinevertices remains an interesting open problem. Stong proved an upper bound within log(k) newlinemultiplicative factor of the minimum. In this work, we prove the following results which newlinemake further progress on this problem: newline1. Large weights do not help in constructing a minimal weighted graph with a prime newlinenumber of spanning trees. newline2. For n and#8805; 6 and 1 and#8804; k and#8804; n2, n vertices suffice for constructing a graph with k newlineminimum spanning trees. newline3. Each of the following intervals (integral ranges) newline[1, n], [n + 1, n2], . . . , [nnand#8722;3 + 1, nnand#8722;2] newlinehas at least one integer k such that there is a weighted graph with n vertices having newlineexactly k MSTs. newline