Maximizing spanning trees in almost complete graphs
Bryan Gilbert, Wendy J. Myrvold · Networks · 1997
We examine the family of graphs whose complements are a union of paths and cycles and develop a very simple algebraic technique for comparing the number of spanning trees. With our algebra, we can obtain a simple proof of a result of Kel'mans that evening out path lengths increases the number of spanning trees in the complement graph. We provide similar characterizations for cycles. The theorems that we develop enable us to characterize the graphs in this family with a maximum number of spanning trees. © 1997 John Wiley & Sons, Inc. Networks 30:23–30, 1997