Graph Theory Lessons
Lesson 19:
Tripartite Graphs
In the same way as with the bipartite graphs, if we
can divide the vertex set into three disjoint non 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 a tripartite graph where every pair of vertices that are
not in the same set of the partition is adjacent.
We represent a 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. Figure 19.1 shows
K2, 3, 3.
|
|
|
Fig 19.1, Complete tripartite graph K2, 3, 3
|
|
Java Web Start Activity:
Use the Java Web Start application below to look at more examples of
complete tripartite graphs.
Petersen Activity:
You will need to use the program to answer the questions so here is how
you get a complete tripartite graph: Select Graph | Named Graph
| Complete | Complete Tripartite Graph and
you will be asked to input r, s, and t. If for instance you input
r=12, s=12 and t=12, you will get a
graph like figure 19.2.
Questions:
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?
- Write down the
adjacency
matrix of
K2, 3, 4.
- What is the chromatic number of a complete tripartite graph?
If we can divide the vertex set of a graph into n disjoint
non empty sets
V1,
V2,...
and Vn so that vertices in the same set
are not adjacent we get an
n-partite graph.
A
complete n-partite
graph is an n-partite graph where every pair of vertices that are
not in the same set of the partition is adjacent.
We represent a complete n-partite graph as
Km1, m2,...,mn
where mi is the number of vertices in
Vi. Figure 19.3 shows
K1, 2, 3, 4, 5, 6.
|
|
|
Fig 19.3, Complete 6-partite graph K1, 2, 3, 4, 5, 6
|
|
Question:
Use your program to examine some complete n-partite graphs and each time write down
the total number of edges in the graph. (The
Properties | Statistics
menu item will give you the total number of edges).
following questions:
-
Which complete n-partite graph is isomorphic to the complete graph Kn?
- Consider the graph
Km1, m2,...,mn
where we have the vertices of the graph divided into n disjoint sets
non empty sets
V1,
V2,...
and Vn, with Vi od size
mi as in the definition. Suppose that the total number of vertices is
∑{mi:i=1,2,...,n} = N. Use the
Handshaking Lemma
to show
that the number of edges in
Km1, m2,...,mn
is [N2 - ∑{mi2:i=1,2,...,n}]/2
= [(∑mi)2 - ∑(mi2)]/2
© C. Mawata
