Bipartite Steinhaus graphs (Q5916329)

A Steinhaus matrix is a symmetric 0-1 matrix \([a_{i,j}]_{n\times n}\) such that \(a_{i,j}= 0\) for \(0\leq i\leq n-1\) and \(a_{i,j}\equiv (a_{i- 1,j-1}+ a_{i-1,j})\pmod 2\) for \(1\leq i\leq n-1\). A Steinhaus graph is a graph whose adjacency matrix is a Steinhaus matrix. In this paper Lee and Chang prove that if \(G\) is a Steinhaus graph of order \(n\) with \(v=\min\text{Adj}(0)\), then the following statements are equivalent: (1) \(G\) is bipartite. (2) \(G\) has no triangle. (3) \(\text{Adj}^+(v)= \varnothing\) or \(\text{Adj}^+(v)= \{v+ w\mid f(w)\geq \max\{n- v- w,v\}\}\). They give a new characterization of bipartite Steinhaus graphs. Note that the equivalence of (1) and (2) was also proved by \textit{W. M. Dymáček} [Discrete Math. 59, 9-20 (1986; Zbl 0616.05048)] in an alternative way.