The Number of Spanning Trees in Kn-complements of Quasi-threshold Graphs
<|reference_start|>The Number of Spanning Trees in Kn-complements of Quasi-threshold Graphs: In this paper we examine the classes of graphs whose $K_n$-complements are trees and quasi-threshold graphs and derive formulas for their number of spanning trees; for a subgraph $H$ of $K_n$, the $K_n$-complement of $H$ is the graph $K_n-H$ which is obtained from $K_n$ 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_n-H$ admitting formulas for the number of their spanning trees.<|reference_end|>
@article{nikolopoulos2005the,
    title={The Number of Spanning Trees in Kn-complements of Quasi-threshold Graphs},
    author={Stavros D. Nikolopoulos and Charis Papadopoulos},
    journal={Graphs and Combinatorics 20(3): 383-397, 2004},
    year={2005},
    archivePrefix={arXiv},
    eprint={cs/0502038},
    primaryClass={cs.DM}
}