Characterizations of bipartite Steinhaus graphs (Q1297427)

For a binary sequence \(T=a_{0,0} a_{0,1}\dots a_{0,n}\) with \(a_{0,0}=0\) the Steinhaus graph generated by \(T\) is defined by the adjacency matrix \(A=[a_{i,j}]\) with \[ a_{i,j}=\begin{cases} 0 &\text{if \(0\leq i=j\leq n-1,\)}\\ (a_{i-1,j-1}+a_{i-1,j})\bmod 2 &\text{if \(0<i<j\leq n-1,\)}\\ a_{j,i} &\text{otherwise.}\end{cases} \] Let min\(\text{Adj} (0)\) be the vertex with the smallest number that is adjacent to vertex \(0\), and let \(\text{Adj} ^+(v)\) be the set of all vertices with numbers exceeding \(v\) that are adjacent to \(v\). It is easily shown that a Steinhaus graph is determined uniquely if \(v=\text{minAdj}(0)\) and \(\text{Adj} ^+(v)\) are given. The authors split the bipartite Steinhaus graphs into four classes and characterize each of the classes in terms of \(v\) and \(\text{Adj} ^+(v)\). They also compute the number \(b(n)\) of bipartite Steinhaus graphs with \(n\) vertices in each class and provide a tight bound on \(b(n)\) for \(n\geq 4\) of the form \(\lceil{1\over 8}(17n-22)\rceil\leq b(n)\leq \lfloor{1\over 2}(5n-7)\rfloor\).