This is documentation for Mathematica 8, which was
based on an earlier version of the Wolfram Language.
View current documentation (Version 11.1)

LineGraph

LineGraph[g]
gives the line graph of the graph g.
  • Each vertex in LineGraph[g] corresponds to an edge in 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 vertices in LineGraph[g] are taken to be successive integers starting at 1.
The line graph of a complete graph:
The line graph of a complete graph:
In[1]:=
Click for copyable input
Out[1]=
In[2]:=
Click for copyable input
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:
New in 8