MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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.

Gerhard "Ask Me About System Design" Paseman, 2012.01.27

share|cite|improve this answer
Many thanks. I wonder what kind of properties one could invoke here. Some form of distance-regularity? – Michele Jan 27 '12 at 16:55
Play with it. For starters, take a complete bipartite graph K_n,m and remove all edges from j except the one connecting to i. After looking at that, start adding edges one at a time to j, and see what you get. Good luck. Gerhard "Ask Me About System Design" Paseman, 2012.01.27 – Gerhard Paseman Jan 27 '12 at 16:58
A comment on the more general case: one can parition an arbitrary connected graph into sets I, J and K, and sum over each siet for a given i and j. I'll let professionals such as Brendan McKay tell you how much further you can run with such a set up. Gerhard "Ask Me About System Design" Paseman, 2012.01.27 – Gerhard Paseman Jan 27 '12 at 17:08

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}.$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.