Graph Theory Lessons

graphic graphic graphicLesson 16: Prisms

Get the graph K3 in the program and then click Operations and choose Prism. You should get the graph in Fig 25.

graphic
Fig. 25, Prism(K3).

In general if you have a graph G, we shall define Prism(G) to be the graph obtained by taking two isomorphic copies of G and place edges between vertices that correspond under the isomorphism. So for example the n-cube is Prism((n-1)-cube).
graphic
Fig. 26, The 4-cube is Prism(3-cube).
  1. Suppose a graph G is regular of degree r. Is Prism(G) regular and if so of what degree?
  2. Suppose a graph G has an Euler circuit. Does it follow that Prism(G) must have an Euler circuit? Explain why or why not.
  3. Which of the n-cubes have Euler circuits?
  4. Suppose G is bipartite. Does this imply that Prism(G) is bipartite?
  5. Which of the n-cubes is/are bipartite?
  6. Find the chromatic number of Prism(N(3)). Suppose that X(G)=1 then what is X(Prism(G))?
  7. Suppose that X(G)=c where c > 1. What is X(Prism(G))?
  8. What is X(Prism(Kn)?
  9. Use the program to find a Hamilton circuit in Prism(C7). Suppose that G has a Hamilton circuit. Does this imply that Prism(G) has a Hamilton circuit?

Answers

e-mail: C. Mawata
graphic graphic graphic
© C. Mawata