Formal Definition
Given a graph G, its line graph L(G) is a graph such that
- each vertex of L(G) represents an edge of G; and
- two vertices of L(G) are adjacent if and only if their corresponding edges share a common endpoint ("are adjacent") in G.
That is, it is the intersection graph of the edges of G, representing each edge by the set of its two endpoints.
Read more about this topic: Line Graph
Famous quotes containing the words formal and/or definition:
“I will not let him stir
Till I have used the approvèd means I have,
With wholesome syrups, drugs, and holy prayers,
To make of him a formal man again.”
—William Shakespeare (1564–1616)
“... we all know the wag’s definition of a philanthropist: a man whose charity increases directly as the square of the distance.”
—George Eliot [Mary Ann (or Marian)