Spanning Tree Results for Graphs and Multigraphs

The following sections are included:

• Dedication
• Preface
• Contents

This book is concerned with the calculation of the number of spanning trees of a multigraph using algebraic and analytic techniques. We also include several results on optimizing the number of spanning trees among all multigraphs in a class, i.e., those having a specified number of nodes, n, and edges, e, denoted Ω(n,e) . The problem has some practical use in network reliability theory. Some of the material in this book has appeared elsewhere in individual publications and has been collected here for the purpose of exposition. In preparation, we first collect some relevant graph theoretical and matrix theoretical results.

In this chapter, we explore the algebraic method of computing t(M), the number of spanning trees of a multigraph M. We then apply these techniques to some special families of graphs…

In this chapter, we consider the optimization problem of maximizing the number of spanning trees among all multigraphs in Ω(n,e), i.e., among all multigraphs having n nodes and e edges, for certain values of e. Since a spanning tree is a minimally connected subgraph, multigraphs having more of these are, in some sense, more immune to disconnection by edge failure.

A result of Cheng [Cheng, 1981] in optimization theory states that a product of positive elements having fixed sum A and fixed sum of squares C is maximized when the elements are all the same or "almost" the same. He made use of this result to find the multigraph that maximizes the number of spanning trees for two different values of e, and the following is an exposition and expansion of his treatment.

The following sections are included:

• Characteristic Polynomials of Threshold Graphs
• Minimum Number of Spanning Trees
• Spanning Trees of Split Graphs

When optimizing the number of spanning trees over a class of graphs, the problem is fairly straightforward. If we consider the condition that each pair of nodes has at most one edge between them, and then “relax” that condition to allow for multigraphs (i.e., allow for multiple edges between a pair of nodes), one would surmise that the solution to the problem would be readily attainable. That is simply not the case for the spanning tree problem. In this chapter, we explore some possible approaches to one problem in particular…

Of particular interest is the classification of graphs by the nature of their eigenvalues. In this chapter, we discuss those graphs and multigraphs whose eigenvalues are all integers. There are many such graphs and multigraphs, and this chapter is not intended to be an exhaustive exposition. Much of this material has appeared in earlier chapters of this book.

The following sections are included:

• Bibliography
• Index