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

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
نویسندگان
,