1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Jan 27, 2012 at 16:31

2 Answers 2

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ Many thanks. I wonder what kind of properties one could invoke here. Some form of distance-regularity? $\endgroup$
    – Michele
    Commented Jan 27, 2012 at 16:55
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Jan 27, 2012 at 16:58
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Jan 27, 2012 at 17:08
1
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .