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:
“Michelangelo said to Pope Julius II, “Self negation is noble, self-culture is beneficent, self-possession is manly, but to the truly great and inspiring soul they are poor and tame compared to self-abuse.” Mr. Brown, here, in one of his latest and most graceful poems refers to it in an eloquent line which is destined to live to the end of time—”None know it but to love it, None name it but to praise.””
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)
“In this Journal, my pen is a delicate needle point, tracing out a graph of temperament so as to show its daily fluctuations: grave and gay, up and down, lamentation and revelry, self-love and self-disgust. You get here all my thoughts and opinions, always irresponsible and often contradictory or mutually exclusive, all my moods and vapours, all the varying reactions to environment of this jelly which is I.”
—W.N.P. Barbellion (1889–1919)