gives the line graph of the graph g.

uses rules to specify the graph g.

Details and OptionsDetails 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
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 , has vertices . 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 , 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 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).
Introduced in 2010
| Updated in 2015
Translate this page: