Line graph: Difference between revisions

Revision as of 11:32, 31 October 2022

Revision as of 06:12, 18 December 2022

Line 76:

| volume = 373

| year = 2003

| s2cid = 32070167

| url = https://research.tilburguniversity.edu/en/publications/a9a1857e-13ce-4da7-bcca-b879f9f3215f

}}. 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}})}}.

Line 103 ⟶ 104:

| title = The strong perfect graph conjecture: 40 years of attempts, and its resolution

| volume = 309

| year = 2009| s2cid = 16049392

| year = 2009}}.</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>

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 212 ⟶ 214:

| title = Combinatorial Mathematics: Proceedings of the Third International Conference (New York, 1985)

| volume = 555

| year = 1989| issue = 1
| bibcode = 1989NYASA.555..310M

| s2cid = 86300941

}}.</ref> This operation is known variously as the second truncation,<ref>{{citation|title=Polyhedra: A Visual Approach|first=Anthony|last=Pugh|publisher=University of California Press|year=1976|isbn=9780520030565}}.</ref> degenerate truncation,<ref>{{citation|title=Space Structures—their Harmony and Counterpoint|first=Arthur Lee|last=Loeb|edition=5th|publisher=Birkhäuser|year=1991|isbn=9783764335885}}.</ref> or [[rectification (geometry)|rectification]].<ref>{{mathworld|title=Rectification|id=Rectification}}</ref>

Line 358 ⟶ 361:

| title = Zu einem Isomorphiesatz von H. Whitney für Graphen

| volume = 164

| year = 1966| issue = 3
| s2cid = 119898359

}}.

*{{citation

Line 454 ⟶ 458:

| title = Line graphs of multigraphs and Hamilton-connectedness of claw-free graphs

| volume = 66

| year = 2011}}.| s2cid = 8880045

}}.

*{{citation

| last = Sedláček | first = J.