Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Line graph
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
===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. 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. 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. 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}}
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)