line_graph (694B)
1 # Line graph 2 3 https://en.wikipedia.org/wiki/Line_graph 4 5 The *line graph* of an [undirected_graph] G = (V, E) is the [graph] G' where the [vertices] of G' are E and where there is an edge in G' connecting two edges of E if they share a vertex in G 6 7 They can be recognized in [linear_time] 8 9 They have a [Hamiltonian_cycle] if the original graph has a [Hamiltonian_cycle]: cf [balakrishnan2012textbook], Corollary 6.5.5 and [harary1965eulerian] 10 11 The [graph_square] of the line graph, and the line graph of the [graph_square], are essentially always [Hamiltonian] for [connected_graphs], cf [nebesky1973line] 12 13 Up: [graph_basic_notions] 14 15 See also: [dual_hypergraph], [dual_graph], [incidence_graph]