wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

hamiltonian_cycle_square (289B)

      1 # Hamiltonian cycle square
      2 
      3 On [graphs], it is [NP_hard] to determine if the [graph_square] of an input [graph] is [hamiltonian]
      4 - cf https://en.wikipedia.org/wiki/Graph_power#Computational_complexity 
      5 
      6 On [trees], see [radoszewski2011hamiltonian]
      7 
      8 Up: [hamiltonian_cycle], [graph_square]