Line Graph - Iterating The Line Graph Operator

Iterating The Line Graph Operator

van Rooij & Wilf (1965) consider the sequence of graphs

They show that, when G is a finite connected graph, only four possible behaviors are possible for this sequence:

  • If G is a cycle graph then L(G) and each subsequent graph in this sequence is isomorphic to G itself. These are the only connected graphs for which L(G) is isomorphic to G.
  • If G is a claw K1,3, then L(G) and all subsequent graphs in the sequence are triangles.
  • If G is a path graph then each subsequent graph in the sequence is a shorter path until eventually the sequence terminates with an empty graph.
  • In all remaining cases, the sizes of the graphs in this sequence eventually increase without bound.

If G is not connected, this classification applies separately to each component of G.

Read more about this topic:  Line Graph

Famous quotes containing the words line and/or graph:

    “For a woman to get a rewarding sense of total creation by way of the multiple monotonous chores that are her daily lot would be as irrational as for an assembly line worker to rejoice that he had created an automobile because he tightened a bolt.”
    —Edith Mendel Stern (1901–1975)

    “When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.”
    —Marshall McLuhan (1911–1980)