Line graph: Difference between revisions

Revision as of 13:42, 2 February 2025

Revision as of 18:02, 9 May 2025

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