line_graph (687B)
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 Such graphs can be recognized in [linear_time]. They are always [claw_free] 8 9 - For [hamiltonian_cycles], cf [edge_hamiltonian_cycle] 10 - For [hamiltonian_paths], cf [edge_hamiltonian_path] 11 12 The [graph_square] of the line graph, and the line graph of the [graph_square], are essentially always [Hamiltonian] for [connected_graphs], cf [nebesky1973line] 13 14 Up: [graph_basic_notions] 15 16 See also: [dual_hypergraph], [dual_graph], [incidence_graph]