✦ LIBER ✦

Bipartite Steinhaus graphs

✍ Scribed by Wayne M. Dymacek

Publisher: Elsevier Science
Year: 1986
Tongue: English
Weight: 523 KB
Volume: 59
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(86)90064-6

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

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

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

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

Induced embeddings in Steinhaus graphs

✍ Delahan, Franz A. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 256 KB 👁 2 views

Fix any positive integer n. Let S be the set of all Steinhaus graphs of order n(n -1)/2 + 1. The vertices for each graph in S are the first n(n -1)/2 + 1 positive integers. Let I be the set of all labeled graphs of order n with vertices of the form i(i -1)/2 + 1 for the first n positive integers i.

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

Koszul Bipartite Graphs

✍ Hidefumi Ohsugi; Takayuki Hibi 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 48 KB