Generating strings for bipartite Steinhaus graphs

Let b( n) be the number of bipartite Steinhaus graphs with n vertices. We show that b( n) satisfies the recurrence, b(2) = 2, b(3) = 4, and for k ⩾ 2, b(2 k + 1) = 2 b( k + 1) + 1, b(2 k) = b( k) + b( k + 1). Thus b(n) ⩽ 5 2 n − 7 2 with equality when n is one more than a power of two. To prove this...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 1995-06, Vol.141 (1), p.95-107
Main Authors: Dymàček, Wayne M., Whaley, Tom
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let b( n) be the number of bipartite Steinhaus graphs with n vertices. We show that b( n) satisfies the recurrence, b(2) = 2, b(3) = 4, and for k ⩾ 2, b(2 k + 1) = 2 b( k + 1) + 1, b(2 k) = b( k) + b( k + 1). Thus b(n) ⩽ 5 2 n − 7 2 with equality when n is one more than a power of two. To prove this recurrence, we describe the possible generating strings for these bipartite graphs.
ISSN:0012-365X
1872-681X
DOI:10.1016/0012-365X(93)E0211-L