Acyclic polynomials of graphs

Abstract

For each nonnegative integer $i$, let $a_i$ be the number of $i$-subsets of $V(G)$ that induce an acyclic subgraph of a given graph $G$. We define $A(G,x)={\sum }_{i\ge 0}{a}_i{x}^i$ (the generating function for $a_i$) to be the acyclic polynomial for $G$. After presenting some properties of these polynomials, we investigate the nature and location of their roots.

References in corpus (2)

• On the roots of all-terminal reliability polynomials
• New results on large induced forests in graphs