Results 1 to 4 of 4

Math Help - DIAMETER OF HAMMING GRAPH H(d, 3)

  1. #1
    Newbie
    Joined
    May 2012
    From
    slovenia
    Posts
    14

    Lightbulb DIAMETER 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 ...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Dec 2011
    Posts
    27
    Thanks
    1

    Re: DIAMETER OF HAMMING GRAPH H(d, 3)

    Sketch: Let ( a_1, a_2, ..., a_d)) and ( b_1, b_2, ..., b_d)) vertices in the graph. Then ( a_1, a_2, ..., a_d)) is adjacent to ( b_1, a_2, ..., a_d)). Continuing we have that a path of length d exists from ( a_1, a_2, ..., a_d)) to ( 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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2012
    From
    slovenia
    Posts
    14

    Post Re: DIAMETER OF HAMMING GRAPH H(d, 3)

    did you mean in second sentence that (a1, a2, ..., ad) is adjacent to (b1, b2, ..., bd)?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Dec 2011
    Posts
    27
    Thanks
    1

    Re: 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')
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Hamming Codes
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: January 16th 2012, 01:52 PM
  2. [SOLVED] Diameter 3 Graph and and minimum maximum degree
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 22nd 2011, 02:57 AM
  3. Graph theory proof-diameter/degree relationship
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: September 20th 2010, 04:41 AM
  4. Hamming Code, Parity Matrix
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 28th 2010, 05:03 AM
  5. Hamming weight - Matrices
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 21st 2009, 03:12 AM

Search Tags


/mathhelpforum @mathhelpforum