Generating strings for bipartite Steinhaus graphs (Q1894762)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Generating strings for bipartite Steinhaus graphs |
scientific article |
Statements
Generating strings for bipartite Steinhaus graphs (English)
0 references
18 December 1995
0 references
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\).
0 references
strings
0 references
bipartite graphs
0 references
counting
0 references
Steinhaus graphs
0 references