Analysis of Complex Networks

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

where α(G; r₂, r₃,..., r_ω) denotes the number of induced subgraphs of G isomorphic to the Hamming graph K^r2₂K^r3₃... K^rω_ω, 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; r₂)x^r2₂.

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 K_k(G). Complete subgraphs X, Y ∈K_k(G) on vertices x₁,..., x_k and y₁,..., y_k, 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(x_i, y_j)= p+1 for i ≠ j, and d (x_i, y_i)= p. Relation ~_k is an equivalence relation on K_k(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 ...