Analysis of Complex Networks

13.2 Preliminaries

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 Q₂ is commonly referred as a square, while the three-dimensional hypercube Q₃ 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, α₁(G)=|E(G)|; in other words α₁(G) equals the number of edges of G. Let also α₀(G)=|V(G)|; hence α₀(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⁽¹⁾... u⁽ⁿ⁾