DIR Return Create A Forum - Home
       ---------------------------------------------------------
       knight tours
  HTML https://knighttours.createaforum.com
       ---------------------------------------------------------
       *****************************************************
   DIR Return to: general Hamiltonian cycles problem
       *****************************************************
       #Post#: 43--------------------------------------------------
       wedge-graphs
       By: gsgs Date: December 31, 2025, 2:55 am
       ---------------------------------------------------------
       Definitions:
       -------------
       let a (undirected,simple) wedge-graph be a pair (V,W) consisting
       of n=|V| vertices and |W| triples of different vertices from
       VxVxV
       such that (u,v,w) in W <=> (w,v,u) in W.
       If (V,W) is a wedge graph, then we get a normal graph (V,E) with
       E={(u,v) in VxV such that there is a w in V with (u,v,w) or
       (w,u,v) in W }
       The "associated normal graph".
       So wedge graphs are basically "forbidden transition graphs".
       In a wedge-graph let a W-path of length k>2 be a k-tuple of
       different
       vertices (v1,v2,..,vk) such that v(i),v(i+1),v(i+2) in W for
       each 0<i<k-1.
       A W-path is a W-cycle, iff in addition (v(k-1),v(k),v(1)) and
       (v(k),v(1),v(2)) are in W.
       A W-Hamiltonian-Cycle (WHC) is a W-cycle of length n.
       A W-disjoint-cycle-cover is a collection of vertex disjoint
       cycles
       whose lengths add to n.
       A wedge-graph is called balanced, if for each (u,v,w) in W
       the number |{x in V such that (v,w,x) is in W}| is 2 or 3.
       So there are always 2 or 3 ways to continue a path, as long
       as the target vertices are not yet included.
       A wedge-graph is called r-regular if each vertex in its
       associated normal graph has degree r.
       #Post#: 45--------------------------------------------------
       Re: wedge-graphs
       By: gsgs Date: January 5, 2026, 8:45 am
       ---------------------------------------------------------
       a special group of wedge-graphs are the "station-graphs"
       where each vertex is considered a station with ports=gates where
       edges may enter , and inner edges between the ports to specify
       which ports are compatible in that station.
       So , let a station-graph S =(V,E,S_) be a simple,undirected
       graph (V,E)
       together with a partition S_ of its |V|=N vertices into |S_|=n
       parts=stations.
       Edges (u,v) where u and v are in the same part are called inner
       edges,
       other edges are called outer edges.
       Let its quotient graph be the graph whose vertices are the n
       stations
       and an edge whenever there was any outer edge between those
       stations.
       Let its wedge-graph (S_,W) be the graph whose vertices are the n
       stations
       and wedges (u,v,w) iff there were outer edges (u1,v1) and
       (v2,w1) in S
       with u1 in u , w1 in w , v1 and v2 in v and an inner edge
       (v1,v2) in S.
       Now a wedge-Hamiltonian-cycle in W corresponds to a cycle in S
       of
       length 2n with alternating inner and outer edges in S.
       *****************************************************