# Two conjectures about the diameter of the generalized Hamming graphs on distance $r\geq 1$.

Let $H_{n,r}$ the graph whose vertices are the vectors of $\mathbb{F}_2^n$ and there exists an edge between $x$ and $y$ if and only if the Hamming distance $d(x,y)$ is equal exactly to $r$.

Q1: Could I say that its diameter verifies $d(H_{n,r}) \leq n$?

These graph are $\binom{n}{r}$-regular, then I could say that the length of a path cannot exceed $\binom{n}{r}$ in the hypothesis when, from a vertex $v$, I can pass through distinct vectors of $\mathbb{F}_2^n$ adding to $v$, at each step of my path, any of the vectors of weight $r$ that I did not add previously, thus exhausting the $\binom{n}{r}$ vectors of weight $r$. From this reasoning I can say that

Q2: $d(H_{n,r}) \leq \binom{n}{r}$?

The case $r=1$, the hypercube, covers both inequalities: from this observation originates my conjectures.

NOTE: for $r$ even and $r=0,n$, $H_{n,r}$ is not connected, then we speak about diameter only for $r$ odd and $1\leq r <n$.

## 1 Answer

First, if $X$ is a graph with diameter $d$, then $d+1$ is a lower bound on the number of distinct eigenvalues. Second, any eigenvector for the $n$-cube is an eigenvector for $H_{n,r}$. Since the $n$-cube has exactly $n+1$ distinct eigenvalues, it follows that any component of $H_{n,r}$ has diameter at most $n$. [The diameter bound is standard, google "adjacency algebra". The second statement follows from the fact that the adjacency matrix of $H_{n,r}$ is a polynomial of degree $r$ in the adjacency matrix of the $n$-cube.]

• This is a brilliant way to deal with my problem. Unfortunately I don't know anything about adjacency algebra. Do you know where I can see an explanation/proof that the adjacency matrix of $H_{n,r}$ is a polynomial of degree $r$ in the adjacency matrix of the $n-$cube?? It doesn't seem straightforward to me! Many thanks – ilmarchese Aug 22 '16 at 13:49
• From your observation, we get a direct proof of $Q1$ observing that the eigenvalues $\lambda_a^{n,r}$ of $H_{n,r}$ are the Krawtchouk Polynomials in $(n,r,a)$ and, fixing $n,r$, depends only on $0\leq a \leq n$. Then we can have at maximum $n+1$ values for $a$ and then at maximum $n+1$ distinct eigenvalues for $H_{n,r}$, thus $d \leq n$. – ilmarchese Aug 22 '16 at 14:03
• @ilmarchese: if $A_r$ is the adjacency matrix of $H_{n,r}$, then $A_1A_r$ is a linear combination of $A_{r-1}$ and $A_{r+1}$; this gives recurrence for $A_{r+1}$ in terms of $A_r$ and $A_{r-1}$. As for the adjacency algebra, see the wikipedia page. – Chris Godsil Aug 22 '16 at 14:06