THIS IS DOCUMENTATION FOR AN OBSOLETE PRODUCT.
SEE THE DOCUMENTATION CENTER FOR THE LATEST INFORMATION.

DOCUMENTATION CENTER SEARCH

BUILT-IN MATHEMATICA SYMBOL

LineGraph

LineGraph[g]
gives the line graph of the graph g.

For an undirected graph g, two vertices in LineGraph[g] are adjacent if their corresponding edges share a common vertex.

For a directed graph g, two vertices in LineGraph[g] are adjacent if their corresponding edges are connected, i.e. the target of one edge is the source of the other edge.

The line graph of a complete graph:

Out[1]=

Out[2]=

LineGraph works with undirected graphs:

Directed graphs:

Works with large graphs:

The number of edges in a graph is equal to the number of vertices in its line graph:

The line graph of a connected graph is connected:

The adjacency matrix of a line graph can be computed by

A maximum independent set in a line graph of g corresponds to the maximum matching of g:

A cycle graph is isomorphic to its line graph:

The line graph of a claw

is a triangle:

The line graph of a path

is isomorphic to

The line graph of a bipartite graph is perfect:

The line graph of a Hamiltonian graph is Hamiltonian:

The line graph of an undirected Eulerian graph is Eulerian:

The line graph of an Eulerian graph is Hamiltonian: