image Graph Theory Lessons image

rule

previous index next Lesson 27: Snakes and Coils in Graphs

The path graph Pn, where n≥2, is the connected graph on n vertices with n-2 vertices of degree 2 and two vertices of degree 1. You can get path graphs in the Petersen program by selecting Graph | Named Graph | Grids | Path Graph". The length of a path graph is the number of edges in the graph so Pn is the path graph of length n-1. If a path graph P is an induced subgraph of a graph G we say that P is an induced path in G.

Questions:
Use the Petersen program to answer the questions that follow. Remember that the menu item for induced subgraphs is Relations | Induced Subgraph.
  1. Find the longest induced path in the Petersen graph
  2. Find the longest induced path in the following platonic graphs:
    1. Tetrahedron
    2. Octahedron
    3. Cube
    4. Icosahedron
    5. Dodecahedron
  3. For what values of p is the path graph Pp an induced subgraph of Pq?
  4. Your classmate claims that if a graph does not have an induced path of length p then for all numbers q > p, the graph does not have an induced path of length q. If you believe that statement, prove that it is true. If you don't believe the statement then prove that it is false.

An important problem in coding theory is involves finding the longest induced path in the n-cube . In this context the induced path is called a snake and the problem is often called the snake-in-the-box problem. As the dimension of the cube becomes higher the problem takes a very long time to solve even with powerful computers. The figure below shows the path P14 as an induced subgraph of the 5-cube.

A snake of length 13 in the 5-cube
Questions:
  1. Use the Petersen program to find the longest snake in the following n-cubes:
    1. 3-cube
    2. 4-cube
    3. 5-cube
    4. 6-cube (this might take a while)

A similar problem to the snake-in-the-box problem involves finding the longest induced cycle in the n-cube. In this context the induced cycle is called a coil and the problem is often called the coil-in-the-box problem. The figure below shows the circuit C14 as an induced subgraph of the 5-cube.

A coil of length 14 in the 5-cube
Questions:
  1. Your classmate claims that if a graph does not have an induced cycle of length p then for all numbers q > p, the graph does not have an induced cycle of length q. If you believe that statement, prove that it is correct. Otherwise prove that the statement is incorrect.
  2. Use the Petersen program to find the longest coil in the n-cubes. To give you some guidance you are given upper bounds on the answers
    1. 3-cube
    2. 4-cube (The length is less than 10)
    3. 5-cube (The length is less than 20)
    4. 6-cube (The length is less than 27)

Answers


© C. Mawata