Induced subgraphs of hypercubes

Details Induced subgraphs of hypercubes Induced subgraphs of hypercubes

2011-12-13

arxiv.org/abs/1112.3015v1

Mathematics

Combinatorics

16 pages

Scientific paper

Let $Q_k$ denote the $k$-dimensional hypercube on $2^k$ vertices. A vertex in a subgraph of $Q_k$ is {\em 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\leq 2^k$ vertices of $Q_k$ can have, as a function of $k$ and $n$. This is then used to determine $\min(\max(|V(H_1)|, |V(H_2)|))$ where (i) $H_1$ and $H_2$ are induced subgraphs of $Q_k$, and (ii) together they cover all the edges of $Q_k$, that is $E(H_1)\cup E(H_2) = E(Q_k)$.

Affiliated with

Also associated with

No associations

Rating

Induced subgraphs of hypercubes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Induced subgraphs of hypercubes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Induced subgraphs of hypercubes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-223748