کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4656888 | 1632989 | 2014 | 12 صفحه PDF | دانلود رایگان |
Extremal problems involving the enumeration of graph substructures have a long history in graph theory. For example, the number of independent sets in a d-regular graph on n vertices is at most (2d+1−1)n/2d(2d+1−1)n/2d by the Kahn–Zhao theorem [7] and [13]. Relaxing the regularity constraint to a minimum degree condition, Galvin [5] conjectured that, for n⩾2dn⩾2d, the number of independent sets in a graph with δ(G)⩾dδ(G)⩾d is at most that in Kd,n−dKd,n−d.In this paper, we give a lower bound on the number of independent sets in a d -regular graph mirroring the upper bound in the Kahn–Zhao theorem. The main result of this paper is a proof of a strengthened form of Galvinʼs conjecture, covering the case n⩽2dn⩽2d as well. We find it convenient to address this problem from the perspective of G¯. From this perspective, we show that the number of complete subgraphs of a graph G on n vertices with Δ(G)⩽rΔ(G)⩽r, where n=a(r+1)+bn=a(r+1)+b with 0⩽b⩽r0⩽b⩽r, is bounded above by the number of complete subgraphs in aKr+1∪KbaKr+1∪Kb.
Journal: Journal of Combinatorial Theory, Series B - Volume 104, January 2014, Pages 60–71