کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8903707 1632913 2018 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Extremal G-free induced subgraphs of Kneser graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Extremal G-free induced subgraphs of Kneser graphs
چکیده انگلیسی
The Kneser graph KGn,k is a graph whose vertex set is the family of all k-subsets of [n] and two vertices are adjacent if their corresponding subsets are disjoint. The classical Erdős-Ko-Rado theorem determines the cardinality and structure of a maximum induced K2-free subgraph in KGn,k. As a generalization of the Erdős-Ko-Rado theorem, Erdős proposed a conjecture about the maximum cardinality of an induced Ks+1-free subgraph of KGn,k. As the best known result concerning this conjecture, Frankl (2013) [15], when n≥(2s+1)k−s, gave an affirmative answer to this conjecture and also determined the structure of such a subgraph. In this paper, generalizing the Erdős-Ko-Rado theorem and the Erdős matching conjecture, we consider the problem of determining the structure of a maximum family A for which KGn,k[A] has no subgraph isomorphic to a given graph G. In this regard, we determine the size and structure of such a family provided that n is sufficiently large with respect to G and k. Furthermore, for the case G=K1,t, we present a Hilton-Milner type theorem regarding above-mentioned problem, which specializes to an improvement of a result by Gerbner et al. (2012) [19].
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series A - Volume 159, October 2018, Pages 269-282
نویسندگان
, ,