کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656888 1632989 2014 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The maximum number of complete subgraphs in a graph with given maximum degree
ترجمه فارسی عنوان
حداکثر تعداد زیرگراف های کامل در یک گراف با حداکثر درجه داده شده
کلمات کلیدی
مجموعه مستقل، زیرگراف کامل شمارش فوق العاده
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 104, January 2014, Pages 60–71
نویسندگان
, ,