leaf_power (724B)
1 # Leaf power 2 3 https://www.graphclasses.org/classes/gc_649.html 4 5 A [graph] where there exists a [tree] and threshold k such that the [edges] of the graph connect the [vertices] at [distance] at most k in the tree 6 7 [Hamiltonian_path] on them is in [PTIME] for each fixed k 8 https://cstheory.stackexchange.com/questions/52305/complexity-of-finding-a-path-visiting-all-leaves-on-a-tree-while-respecting-a-di/52315 9 10 [NP_hardness] of [Hamiltonian_path_problem] is claimed by [IGCSI] from [RDV_graphs] but is in fact open, cf [bergougnoux2026hamiltonicity] 11 12 Variant: [pairwise_compatibility_graph], i.e., the distance is between two thresholds 13 14 Recognizing these graphs is [NP_hard] [duprelatour2025recognizing] 15 16 Up: [graph_family]