Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420975 | Discrete Applied Mathematics | 2007 | 5 Pages |
Abstract
We define the αα-invariant of a finite graph G on n+1n+1 vertices to be the alternating sum α(G)≔fn-fn-1+⋯+(-1)nf0α(G)≔fn-fn-1+⋯+(-1)nf0 where each fifi is the number of spanning forests in G with i edges. The cone G^ on a graph G is obtained by adjoining a new vertex p and then joining each vertex of G to p by a single edge. The main result of this paper is a simple and elegant combinatorial interpretation of α(G^) as the cardinality of the set of all edge-rooted spanning forests in the base graph G . We apply this result to discuss several examples of α(G^) including the complete graphs.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
W. Kook,