Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Parity-regular Steinhaus graphs

Authors: Maxime Augier and Shalom Eliahou
Journal: Math. Comp. 77 (2008), 1831-1839
MSC (2000): Primary 11B75, 05C07, 05C50
Published electronically: December 28, 2007
MathSciNet review: 2398797
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Steinhaus graphs on $ n$ vertices are certain simple graphs in bijective correspondence with binary $ \{\texttt{0,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 $ \texttt{110\ldots110}$ 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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11B75, 05C07, 05C50

Retrieve articles in all journals with MSC (2000): 11B75, 05C07, 05C50

Additional Information

Maxime Augier
Affiliation: Ecole Polytechnique Federale de Lausanne, Lausanne, Switzerland

Shalom Eliahou
Affiliation: LMPA-ULCO, B.P. 699, 62228 Calais, Cedex France

Received by editor(s): February 2, 2006
Received by editor(s) in revised form: April 13, 2007
Published electronically: December 28, 2007
Article copyright: © Copyright 2007 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society