13.2 Preliminaries

For nimages, 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 Qn. The two-dimensional hypercube Q2 is commonly referred as a square, while the three-dimensional hypercube Q3 is commonly referred as a cube.

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)

Get Analysis of Complex Networks now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.