کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8903707 | 1632913 | 2018 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Extremal G-free induced subgraphs of Kneser graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
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
Journal: Journal of Combinatorial Theory, Series A - Volume 159, October 2018, Pages 269-282
نویسندگان
Meysam Alishahi, Ali Taherkhani,