1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Automorphism proof (graph theory)

  1. Mar 5, 2016 #1
    1. The problem statement, all variables and given/known data
    The problem is attached and it's part A. There is no need to put problem 4 hence the problem is fully explained in the file attached

    2. Relevant equations
    Zk is mod k basically.

    3. The attempt at a solution
    I know that we have to prove that the transformation is onto,one to one and preserves adjacency.
    It's one to one because
    T(s1)=T(s2)
    s1+v=s2+v
    s1=s2

    It's onto because
    y=s+v
    y-v=s
    T(s)=T(y-v)=y-v+v=y
    I am not quite sure how to show that it preserves adjacency because I can't apply the concept of hamming distance anymore.
     

    Attached Files:

    Last edited: Mar 5, 2016
  2. jcsd
  3. Mar 5, 2016 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Two vertices are adjacent iff they have identical coordinates in all dimensions except for one.

    Say ##U## and ##V## are adjacent because their coordinates are identical except for the ##j##th one.

    For which, if any, of ##u\in\{1,2,...,n\}## are the ##u##th coordinates of ##T(U)## and ##T(V)## equal?
     
  4. Mar 6, 2016 #3
    Yes except for the jth coordinate?
     
  5. Mar 6, 2016 #4

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes, and what does that tell us about whether T(U) and T(V) are adjacent?
     
  6. Mar 6, 2016 #5
    T(U) and T(V) are still adjacent because all their coordinates are the same except for the jth one.
     
  7. Mar 6, 2016 #6
    I had another problem. I would be glad if you take a look.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Automorphism proof (graph theory)
  1. Graph Theory Proof (Replies: 21)

  2. Graph theory trail proof (Replies: 11)

  3. Graph Theory Proof (Replies: 3)

Loading...