Content deleted Content added
m math formatting Tags: Mobile edit Mobile app edit iOS app edit |
m →Translated properties of the underlying graph: Fix errors from careless use of find & replace |
||
Line 31:
===Translated properties of the underlying graph===
Properties of a graph {{mvar|G}} that depend only on adjacency between edges may be translated into equivalent properties in {{math|''L''(''G'')}} that depend on adjacency between vertices. For instance, a [[Matching (graph theory)|matching]] in {{mvar|G}} is a set of edges no two of which are adjacent, and corresponds to a set of vertices in {{math|''L''(''G'')}} no two of which are adjacent, that is, an [[Independent set (graph theory)|independent set]].<ref name="paschos">{{citation|title=Combinatorial Optimization and Theoretical Computer Science: Interfaces and Perspectives|first=Vangelis Th.|
Thus,
Line 38:
* For a graph {{mvar|G}} with {{mvar|n}} vertices and {{mvar|m}} edges, the number of vertices of the line graph {{math|''L''(''G'')}} is {{mvar|m}}, and the number of edges of {{math|''L''(''G'')}} is half the sum of the squares of the [[degree (graph theory)|degrees]] of the vertices in {{mvar|G}}, minus {{mvar|m}}.<ref>{{harvtxt|Harary|1972}}, Theorem 8.1, p. 72.</ref>
* An [[Independent set (graph theory)|independent set]] in {{math|''L''(''G'')}} corresponds to a [[Matching (graph theory)|matching]] in {{mvar|G}}. In particular, a [[maximum independent set problem|maximum independent set]] in {{math|''L''(''G'')}} corresponds to [[maximum matching]] in {{mvar|G}}. Since maximum matchings may be found in polynomial time, so may the maximum independent sets of line graphs, despite the hardness of the maximum independent set problem for more general families of graphs.<ref name="paschos"/> Similarly, a [[rainbow-independent set]] in {{math|''L''(''G'')}} corresponds to a [[rainbow matching]] in {{mvar|G}}.
* The [[edge chromatic number]] of a graph {{mvar|G}} is equal to the [[vertex chromatic number]] of its line graph {{math|''L''(''G'')}}.<ref>{{citation|title=Graph Theory|volume=173|series=Graduate Texts in Mathematics|first=Reinhard|
* The line graph of an [[edge-transitive graph]] is [[vertex-transitive graph|vertex-transitive]]. This property can be used to generate families of graphs that (like the [[Petersen graph]]) are vertex-transitive but are not [[Cayley graph]]s: if {{mvar|G}} is an edge-transitive graph that has at least five vertices, is not bipartite, and has odd vertex degrees, then {{math|''L''(''G'')}} is a vertex-transitive non-Cayley graph.<ref>{{citation
| last1 = Lauri | first1 = Josef
| |||