Spanning Trees of Ideal Proper Split Graphs

摘要

A graph G is a split graph if its node set can be partitioned into a clique and an independent set. Threshold graphs are split graphs with the added property that for all pairs of nodes u and v in G, N(u) -^s{v} is contained in N(v) -^s{u} whenever deg(u) ≤ deg(v). While there is a formula for the number of spanning trees of threshold graphs, none exist for non-threshold split graphs. We present a formula for the eigenvalues of a certain type of split graph which we call Ideal Proper Split (IPS) graphs. IPS graphs have c nodes of equal degree in the independent set and a clique on n-c nodes in which each node is adjacent to exactly one member of the independent set. After finding the eigenvalues for the Laplacian matrix for such graphs, a corollary to Kirchhojf's well-known Matrix-Tree Theorem leads to the number of spanning trees for these graphs. The eigenvalue formula for IPS graphs is shown to yield a formula for the number of spanning trees for a related split graph as well.