Computer Science – Discrete Mathematics
Scientific paper
2005-02-07
Graphs and Combinatorics 20(3): 383-397, 2004
Computer Science
Discrete Mathematics
13 pages, 2 figures
Scientific paper
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.
Nikolopoulos Stavros D.
Papadopoulos Charis
No associations
LandOfFree
The Number of Spanning Trees in Kn-complements of Quasi-threshold Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Number of Spanning Trees in Kn-complements of Quasi-threshold Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Number of Spanning Trees in Kn-complements of Quasi-threshold Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-129101