DIMACS TR: 95-16
Bipartite Steinhaus Graphs
Authors: Bhaskar DasGupta, Martin Furer
ABSTRACT
Steinhaus graphs are simple undirected graphs in which the first row
of the adjacency matrix A=(a_{r,s}) (excluding the very first entry
which is always 0) is an arbitrary sequence of zeros and ones and the
remaining entries in the upper triangular part of A are defined by
a_{r,s} = ((a_{r-1,s-1} + a_{r-1,s})) mod 2 (for 2 <= r < s <= n). Such
graphs have already been studied for their various properties. In
this paper we characterize bipartite Steinhaus graphs, and use this
characterization to give an exact count as well as linear upper and
lower bounds for the number of such graphs on n vertices. These
results answer affirmatively some questions posed by W.M. Dymacek
(Discrete Mathematics, 59 (1986) pp. 9-20).
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-16.ps.gz
DIMACS Home Page