Chapter 11 Simple Graphs304
Figure 11.3 K 5 : the complete graph on 5 nodes.Figure 11.4 An empty graph with 5 nodes.Ann-node graph containingn 1 edges in sequence is known as aline graphLn.
More formally,Lnhas
V.Ln/Dfv 1 ;v 2 ;:::;vng
and
E.Ln/Dfhv 1 —v 2 i;hv 2 —v 3 i;:::;hvn 1 —vnig
For example,L 5 is pictured in Figure 11.5.
There is also a one-way infinite line graphL 1 which can be defined by letting
the nonnegative integersNbe the vertices with edgeshk—.kC1/ifor allk 2 N.
If we add the edgehvn—v 1 ito the line graphLn, we get a graph called alength-
ncycleCn. Figure 11.6 shows a picture of length-5 cycle.
Figure 11.5 L 5 : a 5-node line graph.