Line Graph

• each vertex of L(G) represents an edge of G; and
• any two vertices of L(G) are adjacent if and only if their corresponding edges are incident, meaning they share a common endvertex, in G.

1. . Create a vertex in L(G) for each edge of G
2. . For each vertex in L(G), add an edge to all of its neighbors -- all the other vertices corresponding to edges in G that touch the vertex at either end of the edge in G.

      *      |      |   *--*--*    \ | /     \|/      * 

       *      /|\     / | \    *--|--*    |\ | /|    | \|/ |    |  *  |     | / \ |    |/   \|    *-----* 

Properties

• The line graph of a connected graph is connected
• $\backslash chi\_E(G)\; =\; \backslash chi\_V(L(G))$, the edge chromatic number of a graph is equal to the vertex chromatic number of its line graph

<< Previous Word Browser Next >>
agate fossil beds national monument bahia hariri list of trick knots prolegomena to any future metaphysics flint hill flint river saint agnan 2004 monaco grand prix list of rivers of the americas by coastline seversky p 35 richard mahoney	saadat hasan manto saint aignan de cramesnil loures charles bell new york state highway 2 nalgene johnsonville sloped armour aniakchak national monument and preserve saint andr d'hbertot mandalay pictures	young guns ii austin o'brien lou diamond phillips saint andr dinamo zagreb piano magic saint aignan le jaillard saint andr sur orne saint arnoult hajduk split o'brien	saint arnoult, calvados saint aubin language freedom movement list of conurbations in the united kingdom flying circus house of commons disqualification act 1975 distraction iogear works councils digital collage a rose for mary