LineGraph
LineGraph
Details and Options
- 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.
- LineGraph works with undirected graphs, directed graphs, and multigraphs.
Background & Context
- LineGraph returns the line graph
of 
, which is the graph whose vertices are the edges of 
and whose vertex adjacencies correspond to the edge adjacencies of 
. More formally, given a graph 
with edges e1,…,em, 
has vertices e1,…,em. For undirected 
, 
is an edge in 
if 
and 
are incident to the same vertex in 
, while for directed 
, 
is an edge in 
if the head of 
is the tail of 
in 
. A line graph is also known as an adjoint graph, conjugate graph, covering graph, derivative graph, derived graph, edge graph, edge-to-vertex dual graph, interchange graph, representative graph, or 
-obrazom graph. - Line graphs are used to translate graph theoretical results about vertices to results about edges. For example, independent edge sets in
are independent vertex sets in 
, the edge chromatic number of 
is equal to the chromatic number of 
, etc. - Line graphs are connected by a number of mathematical relations to their original graphs. The simplest of these is that the number of vertices of
equals the number of edges of 
. In addition, if 
is a simple graph having 
edges and 
vertices with vertex degrees d1,…,dn, then the number of edges in 
is 
. Another relation that allows explicit construction of line graphs is that for 
the incidence matrix of a simple graph 
and 
an m×m identity matrix, the adjacency matrix for 
is given by 
. - Determining whether a graph is a line graph can be done in linear time. A graph
is the line graph of a simple graph or multigraph if and only if there exists a family of cliques such that each vertex in 
is contained in exactly two of them, and each edge in 
is induced by one of them. 
is the line graph of a simple graph if this family of cliques can be formed so that no two vertices of 
lie in the same two cliques. - There is a set of nine forbidden graphs, each having at most six vertices, such that a simple graph is a line graph of some simple graph if and only if it contains no graph in this set as an induced subgraph. This set of forbidden graphs is given by GraphData["Beineke"] and includes the complete bipartite graph
, so line graphs are claw-free. Only six of these forbidden graphs are needed to characterize which simple graphs having maximum degree at least 5 are line graphs (see GraphData["Metelsky"]). - Many important results in graph theory characterize the properties of line graphs. For example, Vizing's theorem implies that if
is a triangle-free simple graph, then the chromatic number of 
is either equal to or one more than the size of a maximum clique in 
, while König's line coloring theorem implies that the line graph 
of a bipartite graph is perfect (i.e. the chromatic number of every induced subgraph of 
equals the size of the largest clique of that subgraph).
Examples
open all close allScope (5)
LineGraph works with undirected graphs:
LineGraph[[image]]LineGraph[[image]]LineGraph[[image]]Use rules to specify the graph:
LineGraph[{1 -> 2, 1 -> 3, 2 -> 4, 3 -> 4, 3 -> 5, 4 -> 6, 5 -> 6}]LineGraph works with large graphs:
g = GridGraph[{10, 10, 10, 10}];LineGraph[g]//EdgeCount//TimingProperties & Relations (11)
The number of edges in a graph is equal to the number of vertices in its line graph:
g = PetersenGraph[5, 2]EdgeCount[g]VertexCount[LineGraph[g]]The line graph of a connected graph is connected:
{g = GridGraph[{3, 4}], LineGraph[g]}ConnectedGraphQ /@ %The adjacency matrix of a line graph can be computed by 
:
g = GridGraph[{2, 3}]m = IncidenceMatrix[g];(Transpose[m].m - 2 IdentityMatrix[EdgeCount[g]])//MatrixPlotAdjacencyMatrix[LineGraph[g]]//MatrixPlotA maximum independent set in a line graph of g corresponds to the maximum matching of g:
g = GridGraph[{2, 3}]FindIndependentVertexSet[LineGraph[g]]FindIndependentEdgeSet[g]A cycle graph is isomorphic to its line graph:
{g = CycleGraph[6], LineGraph[g]}IsomorphicGraphQ@@%The line graph of a claw 
is a triangle:
{g = CompleteGraph[{1, 3}], LineGraph[g]}The line graph of a path 
is isomorphic to 
:
g = PathGraph[Range[20]]IsomorphicGraphQ[LineGraph[g], PathGraph[Range[19]]]The line graph of a bipartite graph is perfect:
g = CompleteGraph[{2, 3}]BipartiteGraphQ[g]LineGraph[g]The line graph of a Hamiltonian graph is Hamiltonian:
{g = CompleteGraph[4], LineGraph[g]}HamiltonianGraphQ /@ %The line graph of an undirected Eulerian graph is Eulerian:
g = CompleteGraph[{2, 4}]EulerianGraphQ[g]EulerianGraphQ[LineGraph[g]]The line graph of an Eulerian graph is Hamiltonian:
g = CompleteGraph[5]EulerianGraphQ[g]HamiltonianGraphQ[LineGraph[g]]
Wolfram Research (2010), LineGraph, Wolfram Language function, https://reference.wolfram.com/language/ref/LineGraph.html (updated 2015).
Text
Wolfram Research (2010), LineGraph, Wolfram Language function, https://reference.wolfram.com/language/ref/LineGraph.html (updated 2015).
CMS
Wolfram Language. 2010. "LineGraph." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/LineGraph.html.
APA
Wolfram Language. (2010). LineGraph. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/LineGraph.html