Article ID Journal Published Year Pages File Type
420975 Discrete Applied Mathematics 2007 5 Pages PDF
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
,