Line graph: Difference between revisions

Revision as of 12:49, 8 January 2025

Latest revision as of 10:55, 7 June 2025

(5 intermediate revisions by 4 users not shown)

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