✦ LIBER ✦

Generating strings for bipartite Steinhaus graphs

✍ Scribed by Wayne M. Dymàček; Tom Whaley

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 473 KB
Volume: 141
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)e0211-l

No coin nor oath required. For personal study only.

✦ Synopsis

Let b(n) be the number of bipartite Steinhaus graphs with n vertices. We show that bin) satisfies the recurrence, b(2)=2, b(3)=4, and for k>~2, b(2k+ 1)=2b(k+ 1)+ 1, b(2k) = b(k) + b(k + 1). Thus b(n) <<, ~zn -~ 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.

📜 SIMILAR VOLUMES

Bipartite Steinhaus graphs

✍ Wayne M. Dymacek 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 523 KB

## Theorem. A Steinhaus graph is bipartite if and only if it has no triangles. Theorem. If G is a bipartite Steinhaus graph (G ~-~) with partitions X and Y, where Ixl-< IYI, then G has an X-saturated matching.

Characterizations of bipartite Steinhaus

Characterizations of bipartite Steinhaus graphs

✍ Gerard J. Chang; Bhaskar DasGupta; Wayne M. Dymàček; Martin Fürer; Matthew Koerl 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 821 KB

We characterize bipartite Steinhaus graphs in three ways by partitioning them into four classes and we describe the color sets for each of these classes. An interesting recursion had previously been given for the number of bipartite Steinhaus graphs and we give two fascinating closed forms for this

Generalized steinhaus graphs

✍ Neal Brand; Margaret Morton 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 584 KB

## Abstract A generalized Steinhaus graph of order __n__ and type __s__ is a graph with __n__ vertices whose adjacency matrix (__a__~i,j~) satisfies the relation magnified image where 2 ≦__i__≦__n__−1, __i__ + __s__(__i__ − 1 ≦ __j__ ≦ __n__, __c__~r,i,j~ ϵ {0,1} for all 0 ≦ __r__ ≦ __s__(__i__) −1

Simple Markov-chain algorithms for gener

Simple Markov-chain algorithms for generating bipartite graphs and tournaments

✍ Ravi Kannan; Prasad Tetali; Santosh Vempala 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 174 KB 👁 2 views

We consider two problems: randomly generating labeled bipartite graphs with a given degree sequence and randomly generating labeled tournaments with a given score sequence. We analyze simple Markov chains for both problems. For the first problem, we cannot prove that our chain is rapidly mixing in g

Probability of diameter two for Steinhau

Probability of diameter two for Steinhaus graphs

✍ Neal Brand; Stephen Curran; Sajal Das; Tom Jacob 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 454 KB

A generalized construction of chromatic

A generalized construction of chromatic index critical graphs from bipartite graphs

✍ Michael Plantholt 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 378 KB

W e prove that any graph with maximum degree n which can be obtained by removing exactly 2n -1 edges from the join K? -K, ,, is n-critical This generalizes special constructions of critical graphs by S Fiorini and H P Yap, and suggests a possible extension of another general construction due to Yap