Line graph: Difference between revisions

Revision as of 10:28, 5 July 2024

Latest revision as of 10:55, 7 June 2025

(6 intermediate revisions by 5 users not shown)

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="140px" heights="140px" 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''

Line 79:

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

| 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

| 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 159 ⟶ 170:

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 295 ⟶ 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 502 ⟶ 514:

| volume = 15

| year = 1978| s2cid = 37062237

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

}}.

*{{citation