Induced subgraphs of hypercubes

Abstract: 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 l e q 2^{k}

vertices of

Q_{k}

can have, as a function of

k

and

n

. This is then used to determine

m i n (m a x (| 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}) c u p E (H_{2}) = E (Q_{k})

.

Recommendations

Cited In (13)

This page was built for publication: Induced subgraphs of hypercubes