Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9515955 | Journal of Combinatorial Theory, Series B | 2005 | 6 Pages |
Abstract
The independence polynomial of a graph G is the function i(G,x)=âk⩾0ikxk, where ik 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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
J.I. Brown, R.J. Nowakowski,