# Hamming graphs and power series

Let $i$ and $h$ be two adjacent nodes in a Hamming graph and let $a$ be any positive real. Let us denote by $d_{ij}$ the distance between node $i$ and node $j$ in the graph. I'm trying to find a compact formula for the following (finite) power series, where $j$ runs over all nodes of the graph:

$$S= \sum_j a^{d_{ij}+d_{hj} }. \tag{1}$$

Is this a studied problem?

If the graph is an $n$-hypercube, which is the case I'm most interested in, it seems that

$$S = \sum_{d=0}^n {{n-1}\choose {d}}a^{2d+1} + {{n-1}\choose {d-1}}a^{2d-1}\tag{2}$$

In fact, if you fix node $i$ and consider all the nodes at distance $d$ from $i$, ${{n-1}\choose {d}}$ of them are at distance $d+1$ from $h$, while the remaining ${{n-1}\choose {d-1}}$ are at distance $d-1$. However, I fail to see now how (2) can be further simplified.

I would appreciate any reference to this problem.

Thank you, M.

-
For the hypercube case S/a should simplify to 2(1+a^2)^(n-1). Gerhard "Warning: Calculation Performed Sans Coffee" Paseman, 2012.01.27 –  Gerhard Paseman Jan 27 '12 at 16:31

For the general case of bipartite graphs and adjacent vetices i and j, the graph partitions into sets I and J where I are those vertices closer to i than to j and vice versa. The desired sum is then (a+1) times the sum over I of weighted distances from i plus (a+1) times a similar sum involving j and J. Now you have to use some nice properties of I and J to get a nice form for the total.

As Gerhard points out, when the graph comes from a hyper-cube with $2^n$ points the sum is $2a(a^2+1)^{n-1}.$ When it comes from a Hamming graph with $s^n$ points the sum is $$(a(s-2)+2)a(a^2(s-1)+1)^{n-1}.$$