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


Two problems on independent sets in graphs
Authors:David Galvin
Affiliation:aDepartment of Mathematics, University of Notre Dame, Notre Dame IN 46556, United States
Abstract:Let it(G) denote the number of independent sets of size t in a graph G. Levit and Mandrescu have conjectured that for all bipartite G the sequence (it(G))t≥0 (the independent set sequence of G) is unimodal. We provide evidence for this conjecture by showing that this is true for almost all equibipartite graphs. Specifically, we consider the random equibipartite graph G(n,n,p), and show that for any fixed p∈(0,1] its independent set sequence is almost surely unimodal, and moreover almost surely log-concave except perhaps for a vanishingly small initial segment of the sequence. We obtain similar results for View the MathML source.We also consider the problem of estimating i(G)=∑t≥0it(G) for G in various families. We give a sharp upper bound on the number of independent sets in an n-vertex graph with minimum degree δ, for all fixed δ and sufficiently large n. Specifically, we show that the maximum is achieved uniquely by Kδ,nδ, the complete bipartite graph with δ vertices in one partition class and nδ in the other.We also present a weighted generalization: for all fixed x>0 and δ>0, as long as n=n(x,δ) is large enough, if G is a graph on n vertices with minimum degree δ then ∑t≥0it(G)xt≤∑t≥0it(Kδ,nδ)xt with equality if and only if G=Kδ,nδ.
Keywords:Independent set polynomial   Stable set polynomial   Unimodal sequence   Random graph
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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