Parity-regular Steinhaus graphs

Abstract:

Steinhaus graphs on $n$ vertices are certain simple graphs in bijective correspondence with binary $\{\mathtt {0},\mathtt {1}\}$-sequences of length $n-1$. A conjecture of Dymacek in 1979 states that the only nontrivial regular Steinhaus graphs are those corresponding to the periodic binary sequences $\mathtt {110}\ldots \mathtt {110}$ of any length $n-1=3m$. By an exhaustive search the conjecture was known to hold up to 25 vertices. We report here that it remains true up to 117 vertices. This is achieved by considering the weaker notion of parity-regular Steinhaus graphs, where all vertex degrees have the same parity. We show that these graphs can be parametrized by an $\mathbb {F}_2$-vector space of dimension approximately $n/3$ and thus constitute an efficiently describable domain where true regular Steinhaus graphs can be searched by computer.