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.5 Hamming Polynomials

Brešar et al. introduced in [16] the Hamming polynomial h(G) of a graph G as the Hamming subgraph counting polynomial. More precisely, the Hamming polynomial of a graph G is defined as

images

where α(G; r2, r3,..., rω) denotes the number of induced subgraphs of G isomorphic to the Hamming graph Kr22imagesKr33images... imagesKrωω, and ω = ω(G), where ω ω(G) denotes the clique number of G.

Cube polynomials are therefore only special case of Hamming polynomials, since c(G, x) = Σr2≥0 α(G; r2)xr22.

Before defining the derivatives of a Hamming polynomial, we first define a relation on the set of all complete subgraphs of G on k vertices, denoted by Kk(G). Complete subgraphs X, Y ∈Kk(G) on vertices x1,..., xk and y1,..., yk, respectively, are in relation ~k if the notation of vertices can be chosen in such a way that there exists an integer p such that d(xi, yj)= p+1 for ij, and d (xi, yi)= p. Relation ~k is an equivalence relation on Kk(G) for a partial Hamming graph, see [21]. Moreover, if G is a partial Hamming graph, then 2 ≤ k ≤ ω, and E is an equivalence class of relation ~k, then ...

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