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

Original · EN

In this paper we examine the classes of graphs whose Kₙ-complements are trees and quasi-threshold graphs and derive formulas for their number of spanning trees; for a subgraph H of Kₙ, the Kₙ-complement of H is the graph Kₙ-H which is obtained from Kₙ by removing the edges of H. Our proofs are based on the complement spanning-tree matrix theorem, which expresses the number of spanning trees of a graph as a function of the determinant of a matrix that can be easily constructed from the adjacency relation of the graph. Our results generalize previous results and extend the family of graphs of the form Kₙ-H admitting formulas for the number of their spanning trees.