TOPICS
Search

Line Graph


LineGraph

A line graph L(G) (also called an adjoint, conjugate, covering, derivative, derived, edge, edge-to-vertex dual, interchange, representative, or theta-obrazom graph) of a simple graph G is obtained by associating a vertex with each edge of the graph and connecting two vertices with an edge iff the corresponding edges of G have a vertex in common (Gross and Yellen 2006, p. 20).

Given a line graph L(G), the underlying graph G is known as the root graph of L(G). The root graph of a simple line graph is unique, except for the case K_3=C_3 (Harary 1994, pp. 72-73).

LineGraphDirected

The line graph of a directed graph G is the directed graph L(G) whose vertex set corresponds to the arc set of G and having an arc directed from an edge e_1 to an edge e_2 if in G, the head of e_1 meets the tail of e_2 (Gross and Yellen 2006, p. 265).

Line graphs are implemented in the Wolfram Language as LineGraph[g]. Precomputed line graph identifications of many named graphs can be obtained in the Wolfram Language using GraphData[graph, "LineGraphName"].

The numbers of simple line graphs on n=1, 2, ... vertices are 1, 2, 4, 10, 24, 63, 166, 471, 1408, ... (OEIS A132220), and the numbers of connected simple line graphs are 1, 1, 2, 5, 12, 30, 79, 227, ... (OEIS A003089).

The following table summarizes some named graphs and their corresponding line graphs.

Line graphs are claw-free.

The line graph of a graph with n nodes, e edges, and vertex degrees d_i contains n^'=e nodes and

 e^'=1/2sum_(i=1)^nd_i^2-e

edges (Skiena 1990, p. 137). The incidence matrix C of a graph and adjacency matrix L of its line graph are related by

 L=C^(T)C-2I,

where I is the identity matrix (Skiena 1990, p. 136).

Krausz (1943) proved that a solution L(H)=G exists for a simple graph G iff G decomposes into complete subgraphs with each vertex of G appearing in at most two members of the decomposition. This theorem, however, is not useful for implementation of an efficient algorithm because of the possibly large number of decompositions involved (West 2000, p. 280).

van Rooij and Wilf (1965) shows that a solution to L(H)=G exists for a simple graph G iff G is claw-free and no induced diamond graph of G has two odd triangles. Here, a triangular subgraph T is said to be even if the neighborhood N(v) and vertex set V(T) intersect in an odd number of points for some v in V(G) and even if N(V) and V(T) intersect in an even number of points for every v in V(G) (West 2000, p. 281).

NonLineGraphs

A simple graph is a line graph of some simple graph iff if does not contain any of the above nine Beineke graphs as a forbidden induced subgraph (van Rooij and Wilf 1965; Beineke 1968; Skiena 1990, p. 138; Harary 1994, pp. 74-75; West 2000, p. 282; Gross and Yellen 2006, p. 405). This statement is sometimes known as the Beineke theorem. These nine graphs are implemented in the Wolfram Language as GraphData["Beineke"]. Of the nine, one has four nodes (the claw graph = star graph S_4 = complete bipartite graph K_(1,3)), two have five nodes, and six have six nodes (including the wheel graph W_6).

NonLineGraphs5

A graph with minimum vertex degree at least 5 is a line graph iff it does not contain any of the above six Metelsky graphs as an induced subgraph (Metelsky and Tyshkevich 1997). These six graphs are implemented in the Wolfram Language as GraphData["Metelsky"].

A graph is not a line graph if the smallest element of its graph spectrum is less than -2 (Van Mieghem, 2010, Liu et al. 2010).

Whitney (1932) showed that, with the exception of K_3 and K_(1,3), any two connected graphs with isomorphic line graphs are isomorphic (Skiena 1990, p. 138).

Lehot (1974) gave a linear time algorithm that reconstructs the original graph from its line graph. Liu et al. (2010) give an O(n^2) algorithm for reconstructing the original graph from its line graph, where n is the number of vertices in the line graph. This algorithm is more time efficient than the efficient algorithm of Roussopoulos (1973).

The line graph of an Eulerian graph is both Eulerian and Hamiltonian (Skiena 1990, p. 138). More information about cycles of line graphs is given by Harary and Nash-Williams (1965) and Chartrand (1968).

LineGraphs

Taking the line graph twice does not return the original graph unless the line graph of a graph G is isomorphic to G itself. In fact, The only connected graph that is isomorphic to its line graph is a cycle graph C_n for n>=3 (Skiena 1990, p. 137). Graph unions of cycle graphs (e.g., 2C_3, C_3+C_4, etc.) are also isomorphic to their line graphs, so the graphs that are isomorphic to their line graphs are the regular graphs of degree 2, and the total numbers of not-necessarily connected simple graphs that are isomorphic to their lines graphs are given by the number of partitions of their vertex count having smallest part >=3, given for n=1, 2, ... by 0, 0, 1, 1, 1, 2, 2, 3, 4, 5, 6, 9, 10, 13, 17, ... (OEIS A026796), the first few of which are illustrated above.


See also

Beineke Graphs, Claw-Free Graph, Metelsky Graphs, Root Graph, Total Graph

Explore with Wolfram|Alpha

References

Beineke, L. W. "Derived Graphs and Digraphs." In Beiträge zur Graphentheorie (Ed. H. Sachs, H. Voss, and H. Walther). Leipzig, Germany: Teubner, pp. 17-33, 1968.Beineke, L. W. "Characterizations of Derived Graphs." J. Combin. Th. 9, 129-135, 1970.Chartrand, G. "On Hamiltonian Line Graphs." Trans. Amer. Math. Soc. 134, 559-566, 1968.Degiorgi, D. G. and Simon, K. "A Dynamic Algorithm for Line Graph Recognition." In WG '95: Proceedings of the 21st International Workshop on Graph-Theoretic Concepts in Computer Science. London: Springer-Verlag, pp. 37-48, 1995.DistanceRegular.org. "Line Graphs." http://www.distanceregular.org/indexes/linegraphs.html.Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, pp. 20 and 265, 2006.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.Harary, F. and Nash-Williams, C. J. A. "On Eulerian and Hamiltonian Graphs and Line Graphs." Canad. Math. Bull. 8, 701-709, 1965.Krausz, J. "Démonstration nouvelle d'une théorème de Whitney sur les réseaux." Mat. Fiz. Lapok 50, 78-89, 1943.Lehot, P. G. H. "An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph." J. ACM 21, 569-575, 1974.Liu, D.; Trajanovski, S.; and Van Mieghem, P. "Reverse Line Graph Construction: The Matrix Relabeling Algorithm MARINLINGA Versus Roussopoulos's Algorithm." 22 Oct 2010. http://arxiv.org/abs/1005.0943.Metelsky, Yu. and Tyshkevich, R. "On Line Graphs of Linear 3-Uniform Hypergraphs." J. Graph Th. 25, 243-251, 1997.Naor, J. and Novick, M. B. "An Efficient Reconstruction of a Graph from Its Line Graph in Parallel." J. Algorithms 11, 132-143, 1990.Roussopoulos, N. D. "A max{m,n} Algorithm for Determining the Graph H From Its Line Graph G." Info. Proc. Let. 2, 108-112, 1973.Saaty, T. L. and Kainen, P. C. "Line Graphs." §4-3 in The Four-Color Problem: Assaults and Conquest. New York: Dover, pp. 108-112, 1986.Skiena, S. "Line Graph." §4.1.5 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 128 and 135-139, 1990.Sloane, N. J. A. Sequences A003089/M1417, A026796, and A132220 in "The On-Line Encyclopedia of Integer Sequences."Šoltés, Ľ. "Forbidden Induced Subgraphs for Line Graphs." Disc. Math. 132, 391-394, 1994.Van Mieghem, P. Graph Spectra for Complex Networks. Cambridge, England: Cambridge University Press, 2010.van Rooij, A. and Wilf, H. "The Interchange Graph of a Finite Graph." Acta Math. Acad. Sci. Hungar. 16, 263-269, 1965.Roussopoulos, N. D. "A max{m,n} Algorithm for Determining the Graph h from its Line Graph g." Inform. Proc. Lett. 2, 108-112, 1973.West, D. B. "Characterizing Line Graphs." Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 279-282, 2000.Whitney, H. "Congruent Graphs and the Connectivity of Graphs." Amer. J. Math. 54, 150-168, 1932.

Referenced on Wolfram|Alpha

Line Graph

Cite this as:

Weisstein, Eric W. "Line Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/LineGraph.html

Subject classifications