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

Simple item page
dc.creatorNikolopoulos, Stavros D.
dc.creatorPapadopoulos, Charis
dc.date2005-02-07
dc.date.accessioned2026-07-07T03:22:30Z
dc.date.available2026-07-07T03:22:30Z
dc.descriptionIn 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.
dc.description13 pages, 2 figures
dc.identifierhttps://arxiv.org/abs/cs/0502038
dc.identifierhttp://arxiv.org/abs/cs/0502038
dc.identifierGraphs and Combinatorics 20(3): 383-397, 2004
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/32620
dc.subjectDiscrete Mathematics
dc.subjectG.2.1; G.2.2
dc.titleThe Number of Spanning Trees in Kn-complements of Quasi-threshold Graphs
dc.typetext

Files

Collections

arXiv