For *n* ∈ , let [*n*] denote theset {1, 2,..., *n*}. All graphs considered in this chapter are finite and simple. As usual with *V*(*G*) and *E*(*G*) we denote the vertex and edge set, respectively, of a graph *G*. If *G* does not include *H* as an induced subgraph, then we say that *G* is an *H-free graph*.

*The n-dimensional hypercube*, or simply *n-cube*, is a graph that has all *n* tuples of 0s and 1s as its vertices, where two such tuples are adjacent if their Hamming distance is equal to 1. The *Hamming distance* between two *n*-tuples is defined as the number of positions in which these *n*-tuples differ. We denote the *n*-dimensional hypercube by *Q _{n}*. The two-dimensional hypercube

For a graph *G*, let α_{i}(*G*), *i* ≥ 1, denote the number of induced *i*-cubes of *G*. In particular, α_{1}(*G*)=|*E*(*G*)|; in other words α_{1}(*G*) equals the number of edges of *G*. Let also α_{0}(*G*)=|*V*(*G*)|; hence α_{0}(*G*) equals the number of vertices of *G*. The following equality holds for any hypercube (see [27]):

See [46] for other identities related to counting hypercubes in hypercubes and different approaches to proving (13.3). A natural generalization of hypercubes are *Hamming graphs*, whose vertices are *n*-tuples *u* = *u*^{(1)}... *u*^{(n)}

Start Free Trial

No credit card required