DIR Return Create A Forum - Home
       ---------------------------------------------------------
       knight tours
  HTML https://knighttours.createaforum.com
       ---------------------------------------------------------
       *****************************************************
   DIR Return to: general Hamiltonian cycles problem
       *****************************************************
       #Post#: 50--------------------------------------------------
       hamgads
   DIR By: gsgs
       Date: May 21, 2026, 10:56 pm
       ---------------------------------------------------------
       Definition:
       let G=(V,E) and G'=(V'E') be simple,undirected graphs
       G' is called a "hamgad" of G (from "Hamiltonian gadget") iff
       1.) V<V' (subset(
       2.) for all u,v in V : there is a Hamiltonian path from u to v
       in G' ,
       iff there is an edge u-v in G
       3.) V' cannot be partitioned into 2 or more disjoint paths
       starting and ending at vertices from V
       Remark : the trivial path with 1 vertex and no edge does count
       as path in 3.)
       Remark : this is motivated by simplifying Hamiltonian cycle
       search in a
       graph , since hamgads can be replaces by there simpler,smaller
       underlying
       graphs in the SAT-encoding.
       Remark : if G= kP2 (k unconnected edges) then this is the same
       as
       "in-out-subgraphs" as defined here :
  HTML https://arxiv.org/pdf/1702.02623
       The "x9"s from the other thread are just hamgads of G=2P2.
       Puzzle : find a hamgad for G=P3 , the path with 2 edges and 3
       vertices.
       This was posed to the chatbots
       Grok,ChatGPT,Gemini,Claude,Perplexity,
       Only Gemini solved it.
       *****************************************************
       Page 1 of 1