Line graph

The line graph or line graph is a term from graph theory. Defining a given graph of a new graph is created by the exchange of nodes and edges.

Definition

The line graph or line graph of a simple graph in graph theory, the graph with the following properties:

Example

The following example illustrates the construction of the graph edges to a given graph. The graph shown has the vertex set and the edge set.

A new graph is constructed from the original now by each edge of a new node is in ( by the green ellipse on the original edges illustrated). The newly created nodes are connected if and only if the edges were touching in the original graph.

The result of the design is obtained by hiding the original graph. What remains is the line graph.

Re- expressed as quantities are obtained

Properties

• The edge graph of the circuit graph is isomorphic to its output graph. Circle graphs are the only graphs with this property.
• The line graph of the star graph is the complete graph.
• The line graph of a bipartite graph is a perfect graph.
• Each line graph has a Krausz partition.