Hello!

My question is very simple. I know that the diameter of Hamming graph H(d, 3) is d.

I just want to know how to prove this?

Thanks for answers ...(Talking)

Printable View

- May 14th 2012, 01:35 PMlebdimDIAMETER OF HAMMING GRAPH H(d, 3)
Hello!

My question is very simple. I know that the diameter of Hamming graph H(d, 3) is d.

I just want to know how to prove this?

Thanks for answers ...(Talking) - May 14th 2012, 02:34 PMwsldamRe: DIAMETER OF HAMMING GRAPH H(d, 3)
Sketch: Let ($\displaystyle a_1, a_2, ..., a_d)$) and ($\displaystyle b_1, b_2, ..., b_d)$) vertices in the graph. Then ($\displaystyle a_1, a_2, ..., a_d)$) is adjacent to ($\displaystyle b_1, a_2, ..., a_d)$). Continuing we have that a path of length d exists from ($\displaystyle a_1, a_2, ..., a_d)$) to ($\displaystyle b_1, b_2, ..., b_d)$). Thus the minimum eccentricity of a vertex is d. But note that we can do this for any pair so the max eccentricity is d as well. It follows that the diameter is d.

- May 16th 2012, 12:52 PMlebdimRe: DIAMETER OF HAMMING GRAPH H(d, 3)
did you mean in second sentence that (a1, a2, ..., ad) is adjacent to (b1, b2, ..., bd)?

- May 16th 2012, 02:24 PMwsldamRe: DIAMETER OF HAMMING GRAPH H(d, 3)
No, what is written is correct.

Because we are in a Hamming Graph vertices are adjacent if and only if they differ by a single term. So what I am doing is constructing a path using vertices that are known to be adjacent. So constructing the path I am describing actually has 'd' steps, but I only explicitly showed one. (This is the main reason the eccentricity is 'd')