Content deleted Content added
m →Translated properties of the underlying graph: Just link directly to "Whitney isomorphism theorem" |
Whitney provides converse for connected graphs (minus one pair), not all graphs (minus one pair). |
||
Line 53:
| year = 2003}}. Lauri and Scapellato credit this result to Mark Watkins.</ref>
* If a graph {{mvar|G}} has an [[Euler cycle]], that is, if {{mvar|G}} is connected and has an even number of edges at each vertex, then the line graph of {{mvar|G}} is [[Hamiltonian graph|Hamiltonian]]. However, not all Hamiltonian cycles in line graphs come from Euler cycles in this way; for instance, the line graph of a Hamiltonian graph {{mvar|G}} is itself Hamiltonian, regardless of whether {{mvar|G}} is also Eulerian.<ref>{{harvtxt|Harary|1972}}, Theorem 8.8, p. 80.</ref>
* If two simple graphs are [[graph isomorphism|isomorphic]] then their line graphs are also isomorphic. The [[Line graph#Whitney isomorphism theorem|Whitney graph isomorphism theorem]] provides a converse to this for all but one pair of connected graphs.
* In the context of complex network theory, the line graph of a random network preserves many of the properties of the network such as the [[Small-world network|small-world property]] (the existence of short paths between all pairs of vertices) and the shape of its [[degree distribution]].{{sfnp|Ramezanpour|Karimipour|Mashaghi|2003}} {{harvtxt|Evans|Lambiotte|2009}} observe that any method for finding vertex clusters in a complex network can be applied to the line graph and used to cluster its edges instead.
| |||