Line graph: Difference between revisions

Revision as of 05:00, 7 July 2022

Latest revision as of 10:55, 7 June 2025

(27 intermediate revisions by 23 users not shown)

Line 5:

In the [[mathematics|mathematical]] discipline of [[graph theory]], the '''line graph''' of an [[undirected graph]] {{mvar|G}} is another graph {{math|L(''G'')}} that represents the adjacencies between [[edge (graph theory)|edges]] of {{mvar|G}}. {{math|L(''G'')}} is constructed in the following way: for each edge in {{mvar|G}}, make a vertex in {{math|L(''G'')}}; for every two edges in {{mvar|G}} that have a vertex in common, make an edge between their corresponding vertices in {{math|L(''G'')}}.

The name ''line graph'' comes from a paper by {{harvtxt|Harary|Norman|1960}} although both {{harvtxt|Whitney|1932}} and {{harvtxt|Krausz|1943}} used the construction before this.{{sfnp|Hemminger|Beineke|1978|p=273}} Other terms used for the line graph include the '''covering graph''', the '''derivative''', the '''edge-to-vertex dual''', the '''conjugate''', the '''representative graph''', and the '''θ-obrazom''',{{sfnp|Hemminger|Beineke|1978|p=273}} as well as the '''edge graph''', the '''interchange graph''', the '''adjoint graph''', and the '''derived graph'''.<ref name="h72-71">{{harvtxt|Harary|1972}}, p. 71.</ref>

{{harvs|authorlink=Hassler Whitney|first=Hassler|last=Whitney|year=1932|txt}} proved that with one exceptional case the structure of a [[connected graph]] {{mvar|G}} can be recovered completely from its line graph.<ref name="whitney"/> Many other properties of line graphs follow by translating the properties of the underlying graph from vertices into edges, and by Whitney's theorem the same translation can also be done in the other direction. Line graphs are [[claw-free graph|claw-free]], and the line graphs of [[bipartite graph]]s are [[perfect graph|perfect]]. Line graphs are characterized by nine [[forbidden graph characterization|forbidden subgraphs]] and can be recognized in [[linear time]].

Line 12:

==Formal definition==

Given a graph ''{{mvar|G''}}, its line graph {{math|''L''(''G'')}} is a graph such that

* each [[vertex (graph theory)|vertex]] of {{math|''L''(''G'')}} represents an edge of ''{{mvar|G''}}; and

* two vertices of {{math|''L''(''G'')}} are [[Adjacent (graph theory)|adjacent]] if and only if their corresponding edges share a common endpoint ("are incident") in ''{{mvar|G''}}.

That is, it is the [[intersection graph]] of the edges of ''{{mvar|G''}}, representing each edge by the set of its two endpoints.<ref name="h72-71"/>

== Example ==

Line 21:

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).

<gallery widths="135px140px" heights="135px140px" class="skin-invert-image">

File:Line graph construction 1.svg|Graph ''G''

File:Line graph construction 2.svg|Vertices in L(''G'') constructed from edges in ''G''

File:Line graph construction 3.svg|Added edges in L(''G'')

File:Line graph construction 4.svg|The line graph L(''G'')

</gallery>

Line 31:

===Translated properties of the underlying graph===

Properties of a graph {{mvar|G}} that depend only on adjacency between edges may be translated into equivalent properties in {{math|''L''(''G'')}} that depend on adjacency between vertices. For instance, a [[Matching (graph theory)|matching]] in {{mvar|G}} is a set of edges no two of which are adjacent, and corresponds to a set of vertices in {{math|''L''(''G'')}} no two of which are adjacent, that is, an [[Independent set (graph theory)|independent set]].<ref name="paschos">{{citation|title=Combinatorial Optimization and Theoretical Computer Science: Interfaces and Perspectives|first=Vangelis Th.|''L''astlast=Paschos|publisher=John Wiley & Sons|year=2010|isbn=9780470393673|page=394|url=https://books.google.com/books?id=bOMH9fPOicgC&pg=PA394|quotation=Clearly, there is a one-to-one correspondence between the matchings of a graph and the independent sets of its line graph.}}</ref>

Thus,

Line 38:

* For a graph {{mvar|G}} with {{mvar|n}} vertices and {{mvar|m}} edges, the number of vertices of the line graph {{math|''L''(''G'')}} is {{mvar|m}}, and the number of edges of {{math|''L''(''G'')}} is half the sum of the squares of the [[degree (graph theory)|degrees]] of the vertices in {{mvar|G}}, minus {{mvar|m}}.<ref>{{harvtxt|Harary|1972}}, Theorem 8.1, p.&nbsp;72.</ref>

* An [[Independent set (graph theory)|independent set]] in {{math|''L''(''G'')}} corresponds to a [[Matching (graph theory)|matching]] in {{mvar|G}}. In particular, a [[maximum independent set problem|maximum independent set]] in {{math|''L''(''G'')}} corresponds to [[maximum matching]] in {{mvar|G}}. 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.<ref name="paschos"/> Similarly, a [[rainbow-independent set]] in {{math|''L''(''G'')}} corresponds to a [[rainbow matching]] in {{mvar|G}}.

* The [[edge chromatic number]] of a graph {{mvar|G}} is equal to the [[vertex chromatic number]] of its line graph {{math|''L''(''G'')}}.<ref>{{citation|title=Graph Theory|volume=173|series=Graduate Texts in Mathematics|first=Reinhard|''L''astlast=Diestel|publisher=Springer|year=2006|isbn=9783540261834|page=112|url=https://books.google.com/books?id=aR2TMYQr2CMC&pg=PA112}}. Also in [http://diestel-graph-theory.com/basic.html free online edition], Chapter 5 ("Colouring"), p.&nbsp;118.</ref>

* The line graph of an [[edge-transitive graph]] is [[vertex-transitive graph|vertex-transitive]]. This property can be used to generate families of graphs that (like the [[Petersen graph]]) are vertex-transitive but are not [[Cayley graph]]s: if {{mvar|G}} is an edge-transitive graph that has at least five vertices, is not bipartite, and has odd vertex degrees, then {{math|''L''(''G'')}} is a vertex-transitive non-Cayley graph.<ref>{{citation

| last1 = Lauri | first1 = Josef

Line 53:

| year = 2003}}. Lauri and Scapellato credit this result to Mark Watkins.</ref>

* If a graph {{mvar|G}} has an [[Euler cycle]], that is, if {{mvar|G}} is connected and has an even number of edges at each vertex, then the line graph of {{mvar|G}} is [[Hamiltonian graph|Hamiltonian]]. However, not all Hamiltonian cycles in line graphs come from Euler cycles in this way; for instance, the line graph of a Hamiltonian graph {{mvar|G}} is itself Hamiltonian, regardless of whether {{mvar|G}} is also Eulerian.<ref>{{harvtxt|Harary|1972}}, Theorem 8.8, p.&nbsp;80.</ref>

* If two simple graphs are [[graph isomorphism|isomorphic]] then their line graphs are also isomorphic. The [[GraphLine isomorphismgraph#Whitney isomorphism theorem|Whitney graph isomorphism theorem]] provides a converse to this for all but one pair of connected graphs.

* In the context of complex network theory, the line graph of a random network preserves many of the properties of the network such as the [[Small-world network|small-world property]] (the existence of short paths between all pairs of vertices) and the shape of its [[degree distribution]].{{sfnp|Ramezanpour|Karimipour|Mashaghi|2003}} {{harvtxt|Evans|''L''ambiotteLambiotte|2009}} observe that any method for finding vertex clusters in a complex network can be applied to the line graph and used to cluster its edges instead.

===Whitney isomorphism theorem===

[[File:Diamond line graph.svg|thumb|120px|The [[diamond graph]] (left) and its more-symmetric line graph (right), an exception to the strong Whitney theorem]]

If the line graphs of two [[connected graph]]s are isomorphic, then the underlying graphs are isomorphic, except in the case of the triangle graph {{math|''K''{{sub|3}}}} and the [[Claw (graph theory)|claw]] {{math|''K''{{sub|1,3}}}}, which have isomorphic line graphs but are not themselves isomorphic.<ref name="whitney">{{harvtxt|Whitney|1932}}; {{harvtxt|Krausz|1943}}; {{harvtxt|Harary|1972}}, Theorem 8.3, p.&nbsp;72. Harary gives a simplified proof of this theorem by {{harvtxt|Jung|1966}}.</ref>

Line 76:

| volume = 373

| year = 2003

| s2cid = 32070167

| url = https://research.tilburguniversity.edu/en/publications/a9a1857e-13ce-4da7-bcca-b879f9f3215f

| doi-access = free

}}. See in particular Proposition 8, p.&nbsp;262.</ref> They may also be characterized (again with the exception of {{math|''K''{{sub|8}}}}) as the [[strongly regular graph]]s with parameters {{math|srg(''n''(''n'' –− 1)/2, 2(''n'' –− 2), ''n'' –− 2, 4)}}.<ref>{{harvtxt|Harary|1972}}, Theorem 8.6, p.&nbsp;79. Harary credits this result to independent papers by L. C. Chang (1959) and [[Alan Hoffman (mathematician)|A. J. Hoffman]] (1960).</ref> The three strongly regular graphs with the same parameters and spectrum as {{math|''L''(''K''{{sub|8}})}} are the [[Chang graphs]], which may be obtained by [[Two-graph|graph switching]] from {{math|''L''(''K''{{sub|8}})}}.

The line graph of a [[bipartite graph]] is [[perfect graph|perfect]] (see [[Kőnig's theorem (graph theory)|Kőnig's theorem]]), but need not be bipartite as the example of the claw graph shows. The line graphs of bipartite graphs form one of the key building blocks of perfect graphs, used in the proof of the [[strong perfect graph theorem]].<ref>{{citation

Line 103 ⟶ 105:

| title = The strong perfect graph conjecture: 40 years of attempts, and its resolution

| volume = 309

| year = 2009| s2cid = 16049392

| year = 2009}}.</ref> A special case of these graphs are the [[rook's graph]]s, line graphs of [[complete bipartite graph]]s. Like the line graphs of complete graphs, they can be characterized with one exception by their numbers of vertices, numbers of edges, and number of shared neighbors for adjacent and non-adjacent points. The one exceptional case is {{math|''L''(''K''{{sub|4,4}})}}, which shares its parameters with the [[Shrikhande graph]]. When both sides of the bipartition have the same number of vertices, these graphs are again strongly regular.<ref>{{harvtxt|Harary|1972}}, Theorem 8.7, p.&nbsp;79. Harary credits this characterization of line graphs of complete bipartite graphs to Moon and Hoffman. The case of equal numbers of vertices on both sides had previously been proven by Shrikhande.</ref>

| doi-access = free

| year = 2009}}.</ref> A special case of these graphs are the [[rook's graph]]s, line graphs of [[complete bipartite graph]]s. Like the line graphs of complete graphs, they can be characterized with one exception by their numbers of vertices, numbers of edges, and number of shared neighbors for adjacent and non-adjacent points. The one exceptional case is {{math|''L''(''K''{{sub|4,4}})}}, which shares its parameters with the [[Shrikhande graph]]. When both sides of the bipartition have the same number of vertices, these graphs are again strongly regular.<ref>{{harvtxt|Harary|1972}}, Theorem 8.7, p.&nbsp;79. Harary credits this characterization of line graphs of complete bipartite graphs to Moon and Hoffman. The case of equal numbers of vertices on both sides had previously been proven by Shrikhande.</ref> It has been shown that, except for {{math|''C''{{sub|3}}}} , {{math|''C''{{sub|4}}}} , and {{math|''C''{{sub|5}}}} , all connected strongly regular graphs can be made non-strongly regular within two line graph transformations.<ref>

{{cite arXiv

| eprint = 2410.16138

| title = Theoretical Insights into Line Graph Transformation on Graph Learning

| last1 = Yang

| first1 = Fan

| last2 = Huang

| first2 = Xingyue

| year = 2024

| class = cs.LG

}}

</ref> The extension to disconnected graphs would require that the graph is not a disjoint union of {{math|''C''{{sub|3}}}}.

More generally, a graph {{mvar|G}} is said to be a [[line perfect graph]] if {{math|''L''(''G'')}} is a [[perfect graph]]. The line perfect graphs are exactly the graphs that do not contain a [[cycle (graph theory)|simple cycle]] of odd length greater than three.<ref>{{harvtxt|Trotter|1977}}; {{harvtxt|de Werra|1978}}.</ref> Equivalently, a graph is line perfect if and only if each of its [[biconnected component]]s is either bipartite or of the form {{math|''K''{{sub|4}}}} (the tetrahedron) or {{math|''K''{{sub|1,1,''n''}}}} (a book of one or more triangles all sharing a common edge).{{sfnp|Maffray|1992}} Every line perfect graph is itself perfect.{{sfnp|Trotter|1977}}

Line 121 ⟶ 136:

| jstor = 2039666

}}. {{Citation

| last = Las Vergnas | first = M. | authorlinkauthor-link = Michel Las Vergnas

| mr = 0412042

| issue = 2–3–4

Line 152 ⟶ 167:

For an arbitrary graph {{mvar|G}}, and an arbitrary vertex {{mvar|v}} in {{mvar|G}}, the set of edges incident to {{mvar|v}} corresponds to a [[Clique (graph theory)|clique]] in the line graph {{math|''L''(''G'')}}. The cliques formed in this way partition the edges of {{math|''L''(''G'')}}. Each vertex of {{math|''L''(''G'')}} belongs to exactly two of them (the two cliques corresponding to the two endpoints of the corresponding edge in {{mvar|G}}).

The existence of such a partition into cliques can be used to characterize the line graphs: A graph {{mvar|L}} is the line graph of some other graph or multigraph if and only if it is possible to find a collection of cliques in {{mvar|L}} (allowing some of the cliques to be single vertices) that partition the edges of {{mvar|L}}, such that each vertex of {{mvar|L}} belongs to exactly two of the cliques.<ref name="h72-8.4">{{harvtxt|Harary|1972}}, Theorem 8.4, p.&nbsp;74, gives three equivalent characterizations of line graphs: the partition of the edges into cliques, the property of being [[Claw-free graph|claw-free]] and odd [[Diamond graph|diamond]]-free, and the nine forbidden graphs of Beineke.</ref> It is the line graph of a graph (rather than a multigraph) if this set of cliques satisfies the additional condition that no two vertices of {{mvar|L}} are both in the same two cliques. Given such a family of cliques, the underlying graph {{mvar|G}} for which {{mvar|L}} is the line graph can be recovered by making one vertex in {{mvar|G}} for each clique, and an edge in {{mvar|G}} for each vertex in {{mvar|L}} with its endpoints being the two cliques containing the vertex in {{mvar|L}}. By the strong version of Whitney's isomorphism theorem, if the underlying graph {{mvar|G}} has more than four vertices, there can be only one partition of this type.

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

:[[File:LineGraphExampleA.svg|100px|class=skin-invert]]

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.

Line 190 ⟶ 205:

An alternative construction, the [[medial graph]], coincides with the line graph for planar graphs with maximum degree three, but is always planar. It has the same vertices as the line graph, but potentially fewer edges: two vertices of the medial graph are adjacent if and only if the corresponding two edges are consecutive on some face of the planar embedding. The medial graph of the [[dual graph]] of a plane graph is the same as the medial graph of the original plane graph.<ref>{{citation

| last = Archdeacon | first = Dan | authorlinkauthor-link = Dan Archdeacon

| doi = 10.1016/0012-365X(92)90328-D

| issue = 2

Line 212 ⟶ 227:

| title = Combinatorial Mathematics: Proceedings of the Third International Conference (New York, 1985)

| volume = 555

| year = 1989| issue = 1
| bibcode = 1989NYASA.555..310M

| s2cid = 86300941

}}.</ref> This operation is known variously as the second truncation,<ref>{{citation|title=Polyhedra: A Visual Approach|first=Anthony|last=Pugh|publisher=University of California Press|year=1976|isbn=9780520030565}}.</ref> degenerate truncation,<ref>{{citation|title=Space Structures—their Harmony and Counterpoint|first=Arthur Lee|last=Loeb|edition=5th|publisher=Birkhäuser|year=1991|isbn=9783764335885}}.</ref> or [[rectification (geometry)|rectification]].<ref>{{mathworld|title=Rectification|id=Rectification}}</ref>

Line 290 ⟶ 306:

| title = Graph-theoretic concepts in computer science (Aachen, 1995)

| volume = 1017

| year = 1995}}.| isbn = 978-3-540-60618-5

}}.

*{{citation

| last1 = Evans | first1 = T.S.

Line 300 ⟶ 317:

| volume = 80

| issue = 1

| pagespage = 016105

| doi = 10.1103/PhysRevE.80.016105| pmid = 19658772

| bibcode = 2009PhRvE..80a6105E}}.

Line 338 ⟶ 355:

| s2cid = 122473974 | hdl-access = free

}}.

*{{citation|first=F.|last=Harary|authorlinkauthor-link=Frank Harary|title=Graph Theory|publisher=Addison-Wesley|___location=Massachusetts|year=1972|url=http://www.dtic.mil/dtic/tr/fulltext/u2/705364.pdf|contribution=8. Line Graphs|pages=71–83|access-date=2013-11-08|archive-date=2017-02-07|archive-url=https://web.archive.org/web/20170207091815/http://www.dtic.mil/dtic/tr/fulltext/u2/705364.pdf|url-status=dead}}.

*{{citation

| last1 = Hemminger | first1 = R. L.

Line 358 ⟶ 375:

| title = Zu einem Isomorphiesatz von H. Whitney für Graphen

| volume = 164

| year = 1966| issue = 3
| s2cid = 119898359

}}.

*{{citation

Line 378 ⟶ 396:

| year = 1974| issue = 4

| s2cid = 15036484

| doi-access = free

}}.

*{{citation

Line 454 ⟶ 473:

| title = Line graphs of multigraphs and Hamilton-connectedness of claw-free graphs

| volume = 66

| year = 2011}}.| s2cid = 8880045

}}.

*{{citation

| last = Sedláček | first = J.

Line 474 ⟶ 494:

| year = 1982}}.

*{{citation

| last = Trotter | first = L. E., Jr.

| doi = 10.1007/BF01593791

| issue = 2

Line 494 ⟶ 514:

| volume = 15

| year = 1978| s2cid = 37062237

| url = http://infoscience.epfl.ch/record/88504

}}.

*{{citation

Line 543 ⟶ 564:

*[http://graphclasses.org/classes/gc_249.html Line graphs], [http://graphclasses.org/index.html Information System on Graph Class Inclusions]

*{{mathworld | urlname = LineGraph | title = Line Graph}}

{{DEFAULTSORT:Line Graph}}