Bipartite Steinhaus graphs

Abstract

A Steinhaus matrix is a symmetric 0-1 matrix [a(i,j)](nxn) such that a(i,i) = 0 for 0 less than or equal to i less than or equal to n - 1 and a(i,j) = (a(i-1,j-1) + a(i-1,j)) (mod 2) for 1 less than or equal to i < j less than or equal to n-1. A Steinhaus graph is a graph whose adjacency matrix is a Steinhaus matrix. In this paper, we present a new characterization of bipartite Steinhaus graphs.