Induced subgraphs of hypercubes |
| |
Authors: | Geir Agnarsson |
| |
Affiliation: | Department of Mathematical Sciences, George Mason University, MS 3F2, 4400 University Drive, Fairfax, VA 22030, United States |
| |
Abstract: | Let Qk denote the k-dimensional hypercube on 2k vertices. A vertex in a subgraph of Qk is full if its degree is k. We apply the Kruskal–Katona Theorem to compute the maximum number of full vertices an induced subgraph on n≤2k vertices of Qk can have, as a function of k and n. This is then used to determine min(max(|V(H1)|,|V(H2)|)) where (i) H1 and H2 are induced subgraphs of Qk, and (ii) together they cover all the edges of Qk, that is E(H1)∪E(H2)=E(Qk). |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|