Roots of Independence Polynomials of Well Covered Graphs |
| |
Authors: | JI Brown K Dilcher RJ Nowakowski |
| |
Institution: | (1) Department of Mathematics and Statistics, Dalhousie University, Halifax, Nova Scotia, Canada, B3H 3J5;(2) Department of Mathematics and Statistics, Dalhousie University, Halifax, Nova Scotia, Canada, B3H 3J5;(3) Department of Mathematics and Statistics, Dalhousie University, Halifax, Nova Scotia, Canada, B3H 3J5 |
| |
Abstract: | Let G be a well covered graph, that is, all maximal independent sets of G have the same cardinality, and let ik denote the number of independent sets of cardinality k in G. We investigate the roots of the independence polynomial i(G, x) = ikxk. In particular, we show that if G is a well covered graph with independence number , then all the roots of i(G, x) lie in in the disk |z| (this is far from true if the condition of being well covered is omitted). Moreover, there is a family of well covered graphs (for each ) for which the independence polynomials have a root arbitrarily close to – . |
| |
Keywords: | graph independence polynomial root well covered |
本文献已被 SpringerLink 等数据库收录! |
|