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
DOI: https://doi.org/10.1090/S0025-5718-07-02063-7
Published electronically: December 28, 2007
MathSciNet review: 2398797
Full-text PDF Free Access

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?)

  • 1. C. Bailey and W. Dymacek, Regular Steinhaus graphs, Proc. 19th southeast. Conf. Combinatorics, Graph Theory and Computing, Baton Rouge 1988, Congr. Numerantium 66 (1988) 45-47. MR 992886 (90a:05132)
  • 2. G.J. Chang, B. DasGupta, W. Dymacek, M. Fürer, M. Koerlin, Y-S. Lee and T. Whaley, Characterizations of bipartite Steinhaus graphs, Discrete Math. 199, Nos. 1-3 (1999) 11-25. MR 1675907 (2000a:05168)
  • 3. W. Dymacek, Steinhaus graphs, Proc. 10th southeast. Conf. Combinatorics, Graph Theory and Computing, Boca Raton 1979, Vol. I, Congr. Numerantium 23 (1979) 399-412. MR 561065 (81f:05120)
  • 4. W. Dymacek, J-G. Speton and T. Whaley, Planar Steinhaus graphs, Congr. Numerantium 144 (2000) 193-206. MR 1817934 (2001m:05222)
  • 5. S. Eliahou and D. Hachez, On a problem of Steinhaus concerning binary sequences, Experimental Mathematics 13, No. 2 (2004) 215-229. MR 2068895
  • 6. J. Molluzzo, Steinhaus graphs, Theor. Appl. Graphs, Proc. Kalamazoo 1976, Lect. Notes Math. 642 (1978) 394-402. MR 499509 (80e:05092)
  • 7. H. Steinhaus, One Hundred Problems in Elementary Mathematics. Elinsford, NY: Pergamon, 1963. New York: Dover, 1979 (reprint). MR 0157881 (28:1110)

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
Email: maxime.augier@epfl.ch

Shalom Eliahou
Affiliation: LMPA-ULCO, B.P. 699, 62228 Calais, Cedex France
Email: eliahou@lmpa.univ-littoral.fr

DOI: https://doi.org/10.1090/S0025-5718-07-02063-7
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