11.3: Some Common Graphs
- Page ID
- 48368
Some graphs come up so frequently that they have names. A complete graph \(K_n\) has \(n\) vertices and an edge between every two vertices, for a total of \(n(n-1)/2\) edges. For example, \(K_5\) is shown in Figure 11.3.
The empty graph has no edges at all. For example, the empty graph with 5 nodes is shown in Figure 11.4.
An \(n\)-node graph containing \(n_1\) edges in sequence is known as a line graph \(L_n\). More formally, \(L_n\) has
\[\nonumber V(L_n) = \{v_1, v_2, \ldots, v_n\}\]
and
\[\nonumber E(L_n) = \{\langle v_1 - v_2 \rangle, \langle v_2 - v_3 \rangle, \ldots, \langle v_{n-1} - v_n \rangle\}\]
For example, \(L_5\) is pictured in Figure 11.5.
There is also a one-way infinite line graph \(L_{\infty}\) which can be defined by letting the nonnegative integers \(\mathbb{N}\) be the vertices with edges \((k - (k + 1))\) for all \(k \in \mathbb{N}\).
If we add the edge \(\langle v_n - v_1 \rangle\) to the line graph \(L_n\), we get a graph called a length-n cycle \(C_n\). Figure 11.6 shows a picture of length-5 cycle.