Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

calliendra

  • 2 years ago

For a theoretical graph, the n-th cube Q_n is a simple graph whose verices are the 2^n points (x_1...x_n) in R^n. So that for each x_i=0 or 1, and whose two vertices adjacent if thet agree in exactly n-1 coordinates. show that if n>=2 the Q_n has a hamiltonian cycle.

  • This Question is Closed
  1. calliendra
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    • ok. so i am going to use induction and i hasve my base step be N=2 so i have a 2 dimensional cube with 2^2=4 vertives in R^2. with coordinates (00) (01) (10)(11)... which is really a two dimensional square with those coordinates as vertices. i can easily see it is a hamiltonian cycle.true.

  2. calliendra
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    i can even visualize a 3d cube whose eight vertices in R3whose edges are named: (000)(001)(010)(100)(011)(101)(110)(111) create a cube. which creates a hamiltonian cycyle. |dw:1383750838900:dw|

  3. calliendra
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    however when i get to the n and n+1 i can't think of it... i don't know how to PROVE there is a hamiltonian cycle ... unless there is some formula that i can find to guarantee the edge numbers i need....

  4. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy