Line graph: Difference between revisions

Revision as of 18:49, 28 May 2012

Name

The construction outlined here goes by the name of the line graph. Alternate names are the theta-obrazom, the covering graph, the derivative, the edge-to-vertex dual, the conjugate, and the representative graph, as well as the edge graph, the interchange graph, the adjoint graph, and the derived graph.

Definition

Suppose $G$ is an undirected graph. The line graphof $G$ , denoted $L(G)$ , is defined as follows:

The vertex set of $L(G)$ is defined as the edge set of $G$ .
The edges of $L(G)$ are defined as follows: two vertices of $L(G)$ are adjacent if and only if, when viewed as edges of $G$ , they share a common vertex.

@@ Line 2: / Line 2: @@
 The construction outlined here goes by the name of the '''line graph'''. Alternate names are the '''theta-obrazom''', the '''covering graph''', the '''derivative''', the '''edge-to-vertex dual''', the '''conjugate''', and the '''representative graph''', as well as the '''edge graph''', the '''interchange graph''', the '''adjoint graph''', and the '''derived graph'''.
+==Definition==
+Suppose <math>G</math> is an [[undirected graph]]. The '''line graph'''of <math>G</math>, denoted <math>L(G)</math>, is defined as follows:
+# The vertex set of <math>L(G)</matH> is defined as the edge set of <math>G</math>.
+# The edges of <math>L(G)</math> are defined as follows: two vertices of <math>L(G)</math> are adjacent if and only if, when viewed as edges of <math>G</math>, they share a common vertex.