2005/02/07 by Stavros D. Nikolopoulos, Charis Papadopoulos
Computer Science · #cs.DM
published as Graphs and Combinatorics 20(3): 383-397, 2004 · 13 pages, 2 figures
arxiv created 2005/02/07 · arxiv updated 2009/12/01
In this paper we examine the classes of graphs whose Kn-complements are trees and quasi-threshold graphs and derive formulas for their number of spanning trees; for a subgraph H of Kn, the Kn-complement of H is the graph Kn-H which is obtained from Kn 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 Kn-H admitting formulas for the number of their spanning trees.