首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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) = sum ikxk. In particular, we show that if G is a well covered graph with independence number beta, then all the roots of i(G, x) lie in in the disk |z| le beta (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 beta) for which the independence polynomials have a root arbitrarily close to –beta.
Keywords:graph  independence  polynomial  root  well covered
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号