Article ID Journal Published Year Pages File Type
4653641 European Journal of Combinatorics 2013 14 Pages PDF
Abstract

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).

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,