There are several special types of graphs common enough to have been named. For instance, in the last section, we already talked about \(K_n\text{,}\) the complete graph on \(n\) vertices. Here we consider some more special classes of graphs.
Another type of graph is bipartite, a graph whose vertices can be divided into two sets, \(A\) and \(B\text{,}\) with no two vertices in \(A\) adjacent and no two vertices in \(B\) adjacent. The vertices in \(A\) can be adjacent to some or all of the vertices in \(B\text{.}\) If each vertex in \(A\) is adjacent to all the vertices in \(B\text{,}\) then the graph is a complete bipartite graph, and gets a special name: \(K_{m,n}\text{,}\) where \(|A| = m\) and \(|B| = n\text{.}\)
Some graphs are used more than others, and get special names.
The complete graph on \(n\) vertices.
The complete bipartite graph with sets of \(m\) and \(n\) vertices.
The cycle on \(n\) vertices, just one big loop.
The path on \(n\) vertices, just one long path.
If we assign a direction to each edge in a graph we have a directed graph. We only need to alter the definition of a graph slightly to indicate for each edge which vertex comes first. We will use ordered pairs then to describe the edges.
A directed graph is an ordered pair \(G = (V, E)\) consisting of a nonempty set \(V\) (called the vertices) and a set \(E\) (called the edges) of two-element ordered pairs of \(V\text{.}\)
We represent directed graphs by adding an arrow to each edge. For instance, we might represent the graph
with the picture below.
In a directed graph we will want to distinguish between the number of edges coming into a vertex and the number coming out. We will call these the indegree and outdegree.
In a directed graph, the indegree of a vertex is the number of times that vertex appears as the first element of a edge -- that is, the number of edges coming into the vertex. Similarly, the outdegree is the number of times the vertex appears as the second element of an edge -- that is, the number of edges coming out of the vertex.
Find the indegree and outdegree of each vertex in the graph in Figure Figure 2.
Solution| Indegree | Outdegree | |
| a | 1 | 1 |
| b | 1 | 2 |
| c | 2 | 1 |
| d | 1 | 1 |
On the social network Twitter you may "follow" someone whether or not they follow you. Model the situation where Alice follows Barb and Carl; Barb follows Alice and Denise; Carl follows Alice, Barb, and Denise; and Denise follows only Carl.
We will use a directed graph with an arrow pointing from A to B indicating that Alice follows Barb.
Which of the graphs below are bipartite? Justify your answers.
For which \(n \ge 3\) is the graph \(C_n\) bipartite?
Find the indegree and outdegree of each vertex in the directed graph below.
If five teams play in a round robin tournament, show that it is possible for all five teams to tie for first place. Draw the digraph for this situation. Can you do this for six teams?