4 Special Graphs in Graph Theory with Examples
There are four special graphs in graph theory that are fundamental or special. These four graphs are named complete or “fully connected” graph, line graph, star graph, and cycle graph.
The complete graph on N nodes or agents is denoted by K_N . For K_N it is fully connected, meaning that each agent is connected to every other agent. Below I show the K_4 graph and each agent is fully connected to its three neighbors:
Next, the cycle graph denoted by C_N is a cycle on N agents. Below, I show the C_4 graph:
Next, the line graph denoted by L_N is the graph you get if you snip or cut one of C_N ’s edges and fold out the circle into a line. Below I show the the L_4 graph:
Lastly, the star graph on N agents is denoted by S_N , where we have one hub node or center node, and N leaves. Below I show…