𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Characterizations of bipartite Steinhaus graphs

✍ Scribed by Gerard J. Chang; Bhaskar DasGupta; Wayne M. Dymàček; Martin Fürer; Matthew Koerlin; Yueh-Shin Lee; Tom Whaley

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
821 KB
Volume
199
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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 recursion. Also, we exhibit a lower bound, which is achieved infinitely often, for the number of bipartite Steinhaus graphs.

📜 SIMILAR VOLUMES

Bipartite Steinhaus graphs
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.

Generating strings for bipartite Steinha
Generating strings for bipartite Steinhaus graphs
✍ Wayne M. Dymàček; Tom Whaley 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 473 KB

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 descr

A Characterization of Weakly Bipartite G
A Characterization of Weakly Bipartite Graphs
✍ Bertrand Guenin 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 889 KB

A signed graph is said to be weakly bipartite if the clutter of its odd circuits is ideal.

Disconnected Complements of Steinhaus gr
Disconnected Complements of Steinhaus graphs
✍ Wayne M. Dymàček; Matthew Koerlin; Jean-Guy Speton; Tom Whaley; Jennifer Yanulav 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 548 KB