Line graph

In graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, the line graph L(G) of undirected graph G is another graph L(G) that represents the adjacencies between edges of G. The name line graph comes from a paper by although both
and used the
construction before this.
Other terms used for the line graph include edge graph,
the theta-obrazom, the covering graph,
the derivative, the edge-to-vertex dual, the
interchange graph, the adjoint graph, the
conjugate, the derived graph, and the
representative graph.

One of the earliest and most important theorems about line graphs is due to , who proved that with one exceptional case the structure of G can be recovered completely from its line graph. In other words, with that one exception, the entire graph can be deduced from knowing the adjacencies of edges ("lines").

Formal definition

Given a graph G, its line graph L(G) is a graph such that

• each vertex
  Vertex (graph theory)
  In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
  
   of L(G) represents an edge of G; and
• two vertices of L(G) are adjacent if and only if their corresponding edges share a common endpoint ("are adjacent
  Adjacent
  Adjacent is an adjective meaning contiguous, adjoining or abuttingIn geometry, adjacent is when sides meet to make an angle.In graph theory adjacent nodes in a graph are linked by an edge....
  
  ") in G.

That is, it is the intersection graph

Intersection graph

In the mathematical area of graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph may be represented as an intersection graph, but some important special classes of graphs may be defined by the types of sets that are used to form...

 of the edges of G, representing each edge by the set of its two endpoints.

Example construction

The following figures show a graph (left, with blue vertices) and its line graph (right, with green vertices). Each vertex of the line graph is shown labeled with the pair of endpoints of the corresponding edge in the original graph. For instance, the green vertex on the right labeled 1,3 corresponds to the edge on the left between the blue vertices 1 and 3. Green vertex 1,3 is adjacent to three other green vertices: 1,4 and 1,2 (corresponding to edges sharing the endpoint 1 in the blue graph) and 4,3 (corresponding to an edge sharing the endpoint 3 in the blue graph).

Line graphs of convex polyhedra

A source of examples from geometry are the line graphs of the graphs of simple

Cubic graph

In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs....

 polyhedra. Taking the line graph of the graph of the tetrahedron

Tetrahedron

In geometry, a tetrahedron is a polyhedron composed of four triangular faces, three of which meet at each vertex. A regular tetrahedron is one in which the four triangles are regular, or "equilateral", and is one of the Platonic solids...

 one gets the graph of the octahedron

Octahedron

In geometry, an octahedron is a polyhedron with eight faces. A regular octahedron is a Platonic solid composed of eight equilateral triangles, four of which meet at each vertex....

; from the graph of the cube

Cube

In geometry, a cube is a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex. The cube can also be called a regular hexahedron and is one of the five Platonic solids. It is a special kind of square prism, of rectangular parallelepiped and...

 one gets the graph of a cuboctahedron

Cuboctahedron

In geometry, a cuboctahedron is a polyhedron with eight triangular faces and six square faces. A cuboctahedron has 12 identical vertices, with two triangles and two squares meeting at each, and 24 identical edges, each separating a triangle from a square. As such it is a quasiregular polyhedron,...

; from
the graph of the dodecahedron one gets the graph of the icosidodecahedron

Icosidodecahedron

In geometry, an icosidodecahedron is a polyhedron with twenty triangular faces and twelve pentagonal faces. An icosidodecahedron has 30 identical vertices, with two triangles and two pentagons meeting at each, and 60 identical edges, each separating a triangle from a pentagon...

, etc. Geometrically, the operation consists in cutting each vertex of the polyhedron with a plane cutting all edges adjacent to the vertex at their midpoints; it is sometimes named rectification

Rectification (geometry)

In Euclidean geometry, rectification is the process of truncating a polytope by marking the midpoints of all its edges, and cutting off its vertices at those points...

.

If a polyhedron is not simple (it has more than three edges at a vertex) the line graph will be nonplanar, with a clique

Clique (graph theory)

In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...

 replacing each high-degree vertex. The medial graph is a variant of the line graph of a planar graph, in which two vertices of the medial graph are adjacent if and only if the corresponding two edges are consecutive on some face of the planar graph. For simple polyhedra, the medial graph and the line graph coincide, but for non-simple graphs the medial graph remains planar. Thus, the medial graphs of the cube and octahedron are both isomorphic to the graph of the cuboctahedron, and the medial graphs of the dodecahedron and icosahedron

Icosahedron

In geometry, an icosahedron is a regular polyhedron with 20 identical equilateral triangular faces, 30 edges and 12 vertices. It is one of the five Platonic solids....

 are both isomorphic to the graph of the icosidodecahedron.

Properties

Properties of a graph G that depend only on adjacency between edges may be translated into equivalent properties in L(G) that depend on adjacency between vertices. For instance, a matching in G is a set of edges no two of which are adjacent, and corresponds to a set of vertices in L(G) no two of which are adjacent, that is, an independent set

Independent set (graph theory)

In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I...

.

Thus,

• The line graph of a connected graph is connected. If G is connected, it contains a path
  Path (graph theory)
  In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...
  
   connecting any two of its edges, which translates into a path in L(G) containing any two of the vertices of L(G). However, a graph G that has some isolated vertices, and is therefore disconnected, may nevertheless have a connected line graph.
• A maximum independent set in a line graph corresponds to maximum matching in the original graph. Since maximum matchings may be found in polynomial time, so may the maximum independent sets of line graphs, despite the hardness of the maximum independent set problem for more general families of graphs.
• The edge chromatic number of a graph G is equal to the vertex chromatic number of its line graph L(G).
• The line graph of an edge-transitive graph
  Edge-transitive graph
  In the mathematical field of graph theory, an edge-transitive graph is a graph G such that, given any two edges e1 and e2 of G, there is anautomorphism of G that maps e1 to e2....
  
   is vertex-transitive
  Vertex-transitive graph
  In the mathematical field of graph theory, a vertex-transitive graph is a graph G such that, given any two vertices v1 and v2 of G, there is some automorphismf:V \rightarrow V\ such thatf = v_2.\...
  
  .
• If a graph G has an Euler cycle, that is, if G is connected and has an even number of edges at each vertex, then the line graph of G is Hamiltonian. (However, not all Hamiltonian cycles in line graphs come from Euler cycles in this way.)
• Line graphs are claw-free graphs, graphs without an induced subgraph in the form of a three-leaf tree.
• The line graphs of tree
  Tree (graph theory)
  In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
  
  s are exactly the claw-free block graph
  Block graph
  In graph theory, a branch of combinatorial mathematics, a block graph is a type of undirected graph in which every biconnected component is a clique...
  
  .

Characterization and recognition

A graph G is the line graph of some other graph, if and only if it is possible to find a collection of cliques

Clique (graph theory)

In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...

 in G, partitioning the edges of G, such that each vertex of G belongs to exactly two of the cliques. In order to do this, it may be necessary for some of the cliques to be single vertices. By the result of , if G is not a triangle, there can be only one partition of this type. If such a partition exists, we can recover the original graph for which G is a line graph, by creating a vertex for each clique, and connecting two cliques by an edge whenever G contains a vertex belonging to both cliques. Therefore, except for the case of and , if the line graphs of two connected graphs are isomorphic

Graph isomorphism

In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H f \colon V \to V \,\!such that any two vertices u and v of G are adjacent in G if and only if ƒ and ƒ are adjacent in H...

 then the graphs are isomorphic.
used this observation as the basis for a linear time algorithm for recognizing line graphs and reconstructing their original graphs.

For example, this characterization can be used to show that the following graph is not a line graph:

In this example, the edges going upward, to the left, and to the right from the central degree-four vertex do not have any cliques in common. Therefore, any partition of the graph's edges into cliques would have to have at least one clique for each of these three edges, and these three cliques would all intersect in that central vertex, violating the requirement that each vertex appear in exactly two cliques. Thus, the graph shown is not a line graph.

An alternative characterization of line graphs was proven by (first reported without proof in ). He showed that there are nine minimal graphs that are not line graphs, such that any graph that is not a line graph has one of these nine graphs as an induced subgraph. That is, a graph is a line graph if and only if no subset of its vertices induces one of these nine graphs. In the example above, the four topmost vertices induce a claw (that is, a complete bipartite graph

Complete bipartite graph

In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...

 K_1,3), shown on the top left of the illustration of forbidden subgraphs. Therefore, by Beineke's characterization, this example cannot be a line graph. For graphs with minimum degree at least 5, only the six subgraphs in the left and right columns of the figure are needed in the characterization. This result in Metelsky et al. is similar to the results of Line graphs of hypergraphs

Line graphs of hypergraphs

The line graph of a hypergraph is the graph whose vertex set is the set of the hyperedges of the hypergraph, with two edges adjacent when they have nonempty intersection. In other words, the line graph of a hypergraph is the intersection graph of a family of finite sets...

.

Iterating the line graph operator

consider the sequence of graphs
They show that, when G is a finite connected graph, only four possible behaviors are possible for this sequence:

• If G is a cycle graph
  Cycle graph
  In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn...
  
   then L(G) and each subsequent graph in this sequence is isomorphic
  Graph isomorphism
  In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H f \colon V \to V \,\!such that any two vertices u and v of G are adjacent in G if and only if ƒ and ƒ are adjacent in H...
  
   to G itself. These are the only connected graphs for which L(G) is isomorphic to G.
• If G is a claw K_1,3, then L(G) and all subsequent graphs in the sequence are triangles.
• If G is a path graph
  Path graph
  In the mathematical field of graph theory, a path graph or linear graph is a particularly simple example of a tree, namely a tree with two or more vertices that is not branched at all, that is, contains only vertices of degree 2 and 1...
  
   then each subsequent graph in the sequence is a shorter path until eventually the sequence terminates with an empty graph.
• In all remaining cases, the sizes of the graphs in this sequence eventually increase without bound.

If G is not connected, this classification applies separately to each component of G.

Relations to other families of graphs

Every line graph is a claw-free graph. Some of the properties of claw-free graphs are generalizations of those of line graphs.

The line graph of a bipartite graph

Bipartite graph

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...

 is perfect

Perfect graph

In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph....

 (see König's theorem

König's theorem (graph theory)

In the mathematical area of graph theory, König's theorem, proved by Dénes Kőnig in 1931, describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs...

). The line graphs of bipartite graphs form one of the key building blocks of perfect graphs, used in the proof of the perfect graph theorem. A special case is the rook's graph

Rook's graph

In graph theory, a rook's graph is a graph that represents all legal moves of the rook chess piece on a chessboard: each vertex represents a square on a chessboard and each edge represents a legal move...

s, line graphs of complete bipartite graph

Complete bipartite graph

In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...

s.

Multigraphs

The concept of the line graph of G may naturally be extended to the case where G is a multigraph, although in that case Whitney's uniqueness theorem no longer holds; for instance a complete bipartite graph K_1,n has the same line graph as the dipole graph

Dipole graph

In graph theory, a dipole graph is a multigraph consisting of two vertices connected with a number of edges. A dipole graph containing n edges is called the order-n dipole graph, and is denoted by Dn. The order-n dipole graph is dual to the cycle graph Cn.-References:* Jonathan L. Gross and Jay...

 and Shannon multigraph

Shannon multigraph

In the mathematical discipline of graph theory, Shannon multigraphs, named after Claude Shannon by , are a special type of triangle graphs, which are used in the field of edge coloring in particular....

 with the same number of edges.

Line digraphs

It is also possible to generalize line graphs to directed graphs. If G is a directed graph, its directed line graph or line digraph has one vertex for each edge of G. Two vertices representing directed edges from u to v and from w to x in G are connected by an edge from uv to wx in the line digraph when v = w. That is, each edge in the line digraph of G represents a length-two directed path in G. The de Bruijn graph

De Bruijn graph

In graph theory, an n-dimensional De Bruijn graph of m symbols is a directed graph representing overlaps between sequences of symbols. It has mn vertices, consisting of all possible length-n sequences of the given symbols; the same symbol may appear multiple times in a sequence...

s may be formed by repeating this process of forming directed line graphs, starting from a complete directed graph

Complete graph

In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...

.

Weighted line graphs

In a line graph L(G), each vertex of degree k in the original graph G creates k(k-1)/2 edges in the line graph. For many types of analysis this means high degree nodes in G are over represented in the line graph L(G). For instance consider a random walk

Random walk

A random walk, sometimes denoted RW, is a mathematical formalisation of a trajectory that consists of taking successive random steps. For example, the path traced by a molecule as it travels in a liquid or a gas, the search path of a foraging animal, the price of a fluctuating stock and the...

 on the vertices of the original graph G. This will pass along some edge e with some frequency f. On the other hand this edge e is mapped to a unique vertex, say v, in the line graph L(G). If we now perform the same type of random walk on the vertices of the line graph, the frequency with which v is visited can be completely different from f. If our edge e in G was connected to nodes of degree O(k), it will be traversed O(k²) more frequently in the line graph L(G). Put another way, Whitney's

Hassler Whitney

Hassler Whitney was an American mathematician. He was one of the founders of singularity theory, and did foundational work in manifolds, embeddings, immersions, and characteristic classes.-Work:...

 theorem guarantees that the line graph almost always encodes the topology of the original graph G faithfully but it does not guarantee that dynamics on these two graphs have a simple relationship. One solution is to construct a weighted line graph, that is, a line graph with weighted edges. There are several natural ways to do this . For instance if edges d and e in the graph G are incident at a vertex v with degree k, then in the line graph L(G) the edge connecting the two vertices d and e can be given weight 1/(k-1). In this way every edge in G (provided neither end is connected to a vertex of degree '1') will have strength 2 in the line graph L(G) corresponding to the two ends that the edge has in G.

Line graphs of hypergraphs

The edges of a hypergraph

Hypergraph

In mathematics, a hypergraph is a generalization of a graph, where an edge can connect any number of vertices. Formally, a hypergraph H is a pair H = where X is a set of elements, called nodes or vertices, and E is a set of non-empty subsets of X called hyperedges or links...

 may form an arbitrary family of sets

Family of sets

In set theory and related branches of mathematics, a collection F of subsets of a given set S is called a family of subsets of S, or a family of sets over S. More generally, a collection of any sets whatsoever is called a family of sets...

, so the line graph of a hypergraph is the same as the intersection graph

Intersection graph

In the mathematical area of graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph may be represented as an intersection graph, but some important special classes of graphs may be defined by the types of sets that are used to form...

of the sets from the family.