1. Average independence polynomials
- Author
-
Brown, J.I. and Nowakowski, R.J.
- Subjects
- *
POLYNOMIALS , *INDEPENDENCE (Mathematics) , *MATHEMATICAL functions , *DIFFERENTIAL equations - Abstract
Abstract: The independence polynomial of a graph G is the function , where is the number of independent sets of vertices in G of cardinality k. We investigate here the average independence polynomial, where the average is taken over all independence polynomials of (labeled) graphs of order n. We prove that while almost every independence polynomial has a nonreal root, the average independence polynomials always have all real, simple roots. [Copyright &y& Elsevier]
- Published
- 2005
- Full Text
- View/download PDF