LineGraph

LineGraph[g]

gives the line graph of the graph g.

LineGraph[{vw,}]

uses rules vw to specify the graph g.

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 allclose all

Basic Examples  (1)

The line graph of a complete graph:

In[1]:=
Click for copyable input
Out[1]=

Scope  (5)

Properties & Relations  (11)

Neat Examples  (1)

See Also

IncidenceMatrix  AdjacencyMatrix  GraphComplement

Introduced in 2010
(8.0)
| Updated in 2015
(10.3)