# 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:

## Scope(5)

LineGraph works with undirected graphs:

Directed graphs:

Multigraphs:

Use rules to specify the graph:

LineGraph works with large graphs:

## Properties & Relations(11)

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: