Bipartite Steinhaus Graphs

Steinhaus graphs are simple undirected graphs in which the first row of the adjacency matrix A = (a rs ) (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 rs = (a r\Gamma1 s\Gamma1 + a r\Gamma1 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). 1 Introduction. A Steinhaus graph on n vertices is defined as follows. The graph is simple and undirected. The entries in the adjacency matrix A = (a rs ) are defined by the following relationship (where x \Phi y denotes addition modulo 2): a rr = 0 1 r n a 1s = 0 o..