DIMACS TR: 95-16

Bipartite Steinhaus Graphs

Authors: Bhaskar DasGupta, Martin Furer


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