## 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*_{2}, *r*_{3},..., *r*_{ω}) denotes the number of induced subgraphs of *G* isomorphic to the Hamming graph *K*^{r2}_{2}*K*^{r3}_{3}... *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*_{2})*x*^{r2}_{2}.

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*_{1},..., *x*_{k} and *y*_{1},..., *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 ...