wiki_research

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

hamiltonian_cycle_square (408B)

      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 However, in a graph is [biconnected], then its [graph_square] is always [hamiltonian]: this is [Fleischner's_theorem]
      7 
      8 On [trees], see [radoszewski2011hamiltonian]
      9 
     10 Up: [hamiltonian_cycle], [graph_square]