Line graph: Difference between revisions

Revision as of 18:02, 9 May 2025

Latest revision as of 10:55, 7 June 2025

Line 108:

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

| eprint = 2410.16138

| title = Theoretical Insights into Line Graph Transformation on Graph Learning

Line 116:

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

Line 305 ⟶ 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 512 ⟶ 514:

| volume = 15

| year = 1978| s2cid = 37062237

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

}}.

*{{citation