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

111 Views Asked by At

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

There are 1 best solutions below

3
On BEST 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.]