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.
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.
Use the Petersen program to examine some wheel graphs and answer the following questions:
- How many edges does Wn have?
- Which wheel is a complete graph?
- Write down the adjacency matrix for W8.
- What is the chromatic number of Wn?
- Is it possible for Wn to be bipartite?
© C. Mawata