کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4653641 | 1632791 | 2013 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Induced subgraphs of hypercubes
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Let QkQk denote the kk-dimensional hypercube on 2k2k vertices. A vertex in a subgraph of QkQk is full if its degree is kk. We apply the Kruskal–Katona Theorem to compute the maximum number of full vertices an induced subgraph on n≤2kn≤2k vertices of QkQk can have, as a function of kk and nn. This is then used to determine min(max(|V(H1)|,|V(H2)|))min(max(|V(H1)|,|V(H2)|)) where (i) H1H1 and H2H2 are induced subgraphs of QkQk, and (ii) together they cover all the edges of QkQk, that is E(H1)∪E(H2)=E(Qk)E(H1)∪E(H2)=E(Qk).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 34, Issue 2, February 2013, Pages 155–168
Journal: European Journal of Combinatorics - Volume 34, Issue 2, February 2013, Pages 155–168
نویسندگان
Geir Agnarsson,