Editing Line graph (section)

== Properties ==

===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.|last=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,
* The line graph of a [[connected graph]] is connected. If {{mvar|G}} is connected, it contains a [[path (graph theory)|path]] connecting any two of its edges, which translates into a path in {{math|''L''(''G'')}} containing any two of the vertices of {{math|''L''(''G'')}}. However, a graph {{mvar|G}} that has some isolated vertices, and is therefore disconnected, may nevertheless have a connected line graph.<ref>The need to consider isolated vertices when considering the connectivity of line graphs is pointed out by {{harvtxt|Cvetković|Rowlinson|Simić|2004}}, [https://books.google.com/books?id=FA8SObZcbs4C&pg=PA32 p.&nbsp;32].</ref>
* A line graph has an [[articulation point]] if and only if the underlying graph has a [[bridge (graph theory)|bridge]] for which neither endpoint has degree one.<ref name="h72-71"/>
* 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|last=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
 | last2 = Scapellato | first2 = Raffaele
 | isbn = 0-521-82151-7
 | location = Cambridge
 | mr = 1971819
 | page = 44
 | publisher = Cambridge University Press
 | series = London Mathematical Society Student Texts
 | title = Topics in graph automorphisms and reconstruction
 | url = https://books.google.com/books?id=hsymFm0E0uIC&pg=PA44
 | volume = 54
 | 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 [[Line graph#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|Lambiotte|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|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>

As well as {{math|''K''{{sub|3}}}} and {{math|''K''{{sub|1,3}}}}, there are some other exceptional small graphs with the property that their line graph has a higher degree of symmetry than the graph itself. For instance, the [[diamond graph]] {{math|''K''{{sub|1,1,2}}}} (two triangles sharing an edge) has four [[graph automorphism]]s but its line graph {{math|''K''{{sub|1,2,2}}}} has eight. In the illustration of the diamond graph shown, rotating the graph by 90 degrees is not a symmetry of the graph, but is a symmetry of its line graph. However, all such exceptional cases have at most four vertices. A strengthened version of the Whitney isomorphism theorem states that, for connected graphs with more than four vertices, there is a one-to-one correspondence between isomorphisms of the graphs and isomorphisms of their line graphs.<ref>{{harvtxt|Jung|1966}}; {{harvtxt|Degiorgi|Simon|1995}}.</ref>

Analogues of the Whitney isomorphism theorem have been proven for the line graphs of [[multigraph]]s, but are more complicated in this case.<ref name="z97"/>

===Strongly regular and perfect line graphs===
[[File:Line perfect graph.svg|thumb|240px|A line perfect graph. The edges in each biconnected component are colored black if the component is bipartite, blue if the component is a tetrahedron, and red if the component is a book of triangles.]]
The line graph of the complete graph {{mvar|K{{sub|n}}}} is also known as the '''triangular graph''', the [[Johnson graph]] {{math|''J''(''n'', 2)}}, or the [[complement (graph theory)|complement]] of the [[Kneser graph]] {{math|''KG''{{sub|''n'',2}}}}.  Triangular graphs are characterized by their [[Spectral graph theory|spectra]], except for {{math|1=''n'' = 8}}.<ref>{{citation
 | last1 = van Dam | first1 = Edwin R.
 | last2 = Haemers | first2 = Willem H.
 | doi = 10.1016/S0024-3795(03)00483-X
 | journal = Linear Algebra and Its Applications
 | mr = 2022290
 | pages = 241–272
 | title = Which graphs are determined by their spectrum?
 | 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
 | last1 = Chudnovsky | first1 = Maria | author1-link = Maria Chudnovsky
 | last2 = Robertson | first2 = Neil | author2-link = Neil Robertson (mathematician)
 | last3 = Seymour | first3 = Paul | author3-link = Paul Seymour (mathematician)
 | last4 = Thomas | first4 = Robin | author4-link = Robin Thomas (mathematician)
 | doi = 10.4007/annals.2006.164.51
 | issue = 1
 | journal = [[Annals of Mathematics]]
 | pages = 51–229
 | title = The strong perfect graph theorem
 | url = http://annals.princeton.edu/annals/2006/164-1/p02.xhtml
 | volume = 164
 | year = 2006| arxiv = math/0212070| s2cid = 119151552
}}. See also {{citation
 | last1 = Roussel | first1 = F.
 | last2 = Rusu | first2 = I.
 | last3 = Thuillier | first3 = H.
 | doi = 10.1016/j.disc.2009.05.024
 | issue = 20
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 2552645
 | pages = 6092–6113
 | title = The strong perfect graph conjecture: 40 years of attempts, and its resolution
 | volume = 309
 | year = 2009| s2cid = 16049392
 | doi-access = free
 }}.</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
}}
</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}}

===Other related graph families===
All line graphs are [[claw-free graph]]s, graphs without an [[induced subgraph]] in the form of a three-leaf tree.<ref name="h72-8.4"/> As with claw-free graphs more generally, every connected line graph {{math|''L''(''G'')}} with an even number of edges has a [[perfect matching]];<ref>{{Citation
 | last = Sumner | first = David P.
 | doi = 10.2307/2039666
 | mr = 0323648
 | journal = Proceedings of the American Mathematical Society
 | pages = 8–12
 | title = Graphs with 1-factors
 | volume = 42
 | year = 1974
 | issue = 1
 | publisher = American Mathematical Society
 | jstor = 2039666
}}. {{Citation
 | last = Las Vergnas | first = M. | author-link = Michel Las Vergnas
 | mr = 0412042
 | issue = 2–3–4
 | journal = Cahiers du Centre d'Études de Recherche Opérationnelle
 | pages = 257–260
 | title = A note on matchings in graphs
 | volume = 17
 | year = 1975
}}.</ref> equivalently, this means that if the underlying graph {{mvar|G}} has an even number of edges, its edges can be partitioned into two-edge paths.

The line graphs of [[tree (graph theory)|tree]]s are exactly the claw-free [[block graph]]s.<ref>{{harvtxt|Harary|1972}}, Theorem 8.5, p.&nbsp;78. Harary credits the result to [[Gary Chartrand]].</ref> These graphs have been used to solve a problem in [[extremal graph theory]], of constructing a graph with a given number of edges and vertices whose largest tree [[induced subgraph|induced as a subgraph]] is as small as possible.<ref>{{citation
 | last1 = Erdős | first1 = Paul | author1-link = Paul Erdős
 | last2 = Saks | first2 = Michael | author2-link = Michael Saks (mathematician)
 | last3 = Sós | first3 = Vera T. | author3-link = Vera T. Sós
 | doi = 10.1016/0095-8956(86)90028-6
 | issue = 1
 | journal = Journal of Combinatorial Theory, Series B
 | pages = 61–79
 | title = Maximum induced trees in graphs
 | volume = 41
 | year = 1986| doi-access = free
}}.</ref>

All [[eigenvalue]]s of the [[adjacency matrix]] {{mvar|A}} of a line graph are at least −2. The reason for this is that {{mvar|A}} can be written as <math>A = J^\mathsf{T}J - 2I</math>, where {{mvar|J}} is the signless incidence matrix of the pre-line graph and {{mvar|I}} is the identity. In particular, {{math|''A'' + 2''I''}} is the [[Gramian matrix]] of a system of vectors: all graphs with this property have been called generalized line graphs.{{sfnp|Cvetković|Rowlinson|Simić|2004}}