The Number of Spanning Trees in Kn-complements of Quasi-threshold Graphs

Cayley's formula states that there are $n^{n-2}$ spanning trees in the complete graph on $n$ vertices; it has been proved in more than a dozen different ways over its 150 year history. The complete graphs are a special case of threshold graphs, and using Merris' Theorem and the Matrix Tree Theorem, there is a strikingly simple formula for counting the number of spanning trees in a threshold graph on $n$ vertices; it is simply the product, over $i=2,3, ...,n-1$, of the number ...

Kirchhoff's Matrix-Tree Theorem asserts that the number of spanning trees in a finite graph can be computed from the determinant of any of its reduced Laplacian matrices. In many cases, even for well-studied families of graphs, this can be computationally or algebraically taxing. We show how two well-known results from linear algebra, the Matrix Determinant Lemma and the Schur complement, can be used to elegantly count the spanning trees in several significant families of gra...

The weighted spanning tree enumerator of a graph $G$ with weighted edges is the sum of the products of edge weights over all the spanning trees in $G$. In the special case that all of the edge weights equal $1$, the weighted spanning tree enumerator counts the number of spanning trees in $G$. The Weighted Matrix-Tree Theorem asserts that the weighted spanning tree enumerator can be calculated from the determinant of a reduced weighted Laplacian matrix of $G$. That determinant...

(DRAFT VERSION) In this article we present a proof of the famous Kirchoff's Matrix-Tree theorem, which relates the number of spanning trees in a connected graph with the cofactors (and eigenvalues) of its combinatorial Laplacian matrix. This is a 165 year old result in graph theory and the proof is conceptually simple. However, the elegance of this result is it connects many apparently unrelated concepts in linear algebra and graph theory. Our motivation behind this work was ...

We present new short proofs of known spanning tree enumeration formulae for threshold and Ferrers graphs by showing that the Laplacian matrices of such graphs admit triangular rank-one perturbations. We then characterize the set of graphs whose Laplacian matrices admit triangular rank-one perturbations as the class of special 2-threshold graphs, introduced by Hung, Kloks, and Villaamil. Our work introduces (1) a new characterization of special 2-threshold graphs that generali...

A graph is said to be I-eigenvalue free if it has no eigenvalues in the interval I with respect to the adjacency matrix A. In this paper we present two algorithms for generating I-eigenvalue free threshold graphs.

Many extremal problems for graphs have threshold graphs as their extremal examples. For instance the current authors proved that for fixed $k\ge 1$, among all graphs on $n$ vertices with $m$ edges, some threshold graph has the fewest matchings of size $k$; indeed either the lex graph or the colex graph is such an extremal example. In this paper we consider the problem of maximizing the number of matchings in the class of threshold graphs. We prove that the minimizers are what...

For a graph $G$, we associate a family of real symmetric matrices, $S(G)$, where for any $A\in S(G)$, the location of the nonzero off-diagonal entries of $A$ are governed by the adjacency structure of $G$. Let $q(G)$ be the minimum number of distinct eigenvalues over all matrices in $S(G)$. In this work, we give a characterization of all connected threshold graphs $G$ with $q(G)=2$. Moreover, we study the values of $q(G)$ for connected threshold graphs with trace $2$, $3$, $n...

We give new general formulas for the asymptotics of the number of spanning trees of a large graph. A special case answers a question of McKay (1983) for regular graphs. The general answer involves a quantity for infinite graphs that we call "tree entropy", which we show is a logarithm of a normalized determinant of the graph Laplacian for infinite graphs. Tree entropy is also expressed using random walks. We relate tree entropy to the metric entropy of the uniform spanning fo...

We give combinatorial proofs of some enumeration formulas involving labelled threshold, quasi-threshold, loop-threshold and quasi-loop-threshold graphs. In each case we count by number of vertices and number of components. For threshold graphs, we also count by number of dominating vertices, and for loop-threshold graphs we count by number of looped dominating vertices. We also obtain an analog of the Frobenius formula (connecting Eulerian numbers and Stirling numbers of th...