image
Graph Theory Lessons

rule

previous index next Lesson 18: Star Graphs

Suppose we start with n vertices, choose one special vertex and then draw edges from the special vertex to every other vertex. The graph we would obtain is called the star on n vertices, Sn. Figure 18.1 shows the star on ten vertices, S10.

Star on 10 vertices
Fig 18.1, The star S10


Java Web Start Activity:
To get examples of star 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.


Petersen activity:
To get a star graph in the Petersen program use the menu options Graph | Named Graph | Trees | Star. Take a look at a few of the graphs Sn for other values of n and then answer the questions below.

the star graph on 30 vertices
Fig 18.2, The graph S30


Questions:
Use the Petersen program to examine some star graphs and answer the following questions:
  1. What is the chromatic number of S3, S5, S8
  2. Are stars bipartite ?
  3. Which complete bipartite graph is isomorphic to Sn?

Answers


© C. Mawata