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 a star on n vertices,
Sn. To get
S10 using the program click Graph and Star. When
asked how many vertices input 10. You will get a graph
as in figure 14
Fig. 14, The star S10
In the same way you can get graphs Sn for other values of
n.
Which complete bipartite graph is
isomorphic to Sn?
In the same way as with the bipartite graphs, if we
can divide the vertex set into three disjoint on empty sets V1 ,
V2 and V3 so that vertices in the same set
are not adjacent we get a tripartite graph. A complete
tripartite graph is one
where we can divide the vertex set into three sets V1 ,
V2 and V3 and every pair of vertices that are
not in the same set are adjacent. We represent the complete tripartite graph as
Kr,s,t where r is the number of vertices in
V1, s the number of vertices in
V2 and t the number of vertices in
V3. If you select Graph and Complete and
Complete Tripartite you will be asked to input r,s, and t. If for instance you input
r=2, s=3 and t=3, you will get a graph like figure 15
Fig. 15, K2,3,3 properly colored.
Use your program to examine some complete tripartite graphs and answer the
following questions:
How many edges does Kr,s,t have?
If a complete tripartite graph Kr,s,t is regular, what can you say
about r,s, and t?
Which complete tripartite graph is regular of degree m?
Why can't a complete tripartite graph be trivalent?
Graph Theory Lessons
Lesson 10: Stars and
Tripartite Graphs
