Generating strings for bipartite Steinhaus graphs (Q1894762): Difference between revisions

If \(b(n)\) is the number of bipartite Steinhaus graphs with \(n\) vertices, the authors prove the recurrence relations \(b(2)= 2\), \(b(3)= 4\) and \(b(2k)= b(k)+ b(k+ 1)\), \(b(2k+ 1)= 2b(k+ 1)+ 1\) for any \(k\geq 2\). Whence, they derive that \(b(n)\leq (5n- 7)/2\), with equality if \(n\) has the form \(2^m+ 1\) for some integer \(m\).