image
Graph Theory Lessons

rule

previous index next Lesson 22: Wheel Graphs

A wheel on n vertices Wn is a graph with n vertices x1, x2,..., xn, with x1 having degree n-1 and all the other vertices having degree 3. The vertex x1 is adjacent to all the other vertices, and for i=2, ..., n-1, xi is adjacent to xi+1, and xn-1 is adjacent to x2. We shall assume that n>3 in all the problems.

Java Web Start Activity:
To get examples of wheel graphs, launch the Java Web Start application by clicking on the link below this paragraph. Once the application is running, click on the + button to increase the number of vertices. The - button decreases the number of vertices.

Java Web Start Application 22.1: Wheel graphs

Petersen activity:
To get a wheel graph in the Petersen program use the menu options Graph | Named Graph | Wheel. Take a look at a few of the graphs Wn for other values of n. The vertices don't have to be arranged as a wheel.

A wheel on 51 vertices
Fig 22.1, The wheel graph W51

Questions:
Use the Petersen program to examine some wheel graphs and answer the following questions:
  1. How many edges does Wn have?
  2. Which wheel is a complete graph?
  3. Write down the adjacency matrix for W8.
  4. What is the chromatic number of Wn?
  5. Is it possible for Wn to be bipartite?

Answers


© C. Mawata