O'Reilly logo

Analysis of Complex Networks by Frank Emmert-Streib, Matthias Dehmer

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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]):

images

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)

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required