✦ LIBER ✦

Generalized steinhaus graphs

✍ Scribed by Neal Brand; Margaret Morton

Publisher: John Wiley and Sons
Year: 1995
Tongue: English
Weight: 584 KB
Volume: 20
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190200105

No coin nor oath required. For personal study only.

✦ Synopsis

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 and c~s(i)−1,i,j~ = 1. The values of s(i) and c~r,i,j~ are fixed but arbitrary. Generalized Steinhaus graphs in which each edge has probability ½ are considered. In an article by A. Blass and F. Harary [“Properties of Almost All Graphs and Complexes,” Journal of Graph Theory, Vol. 3 (1976), pp. 225–240], a collection of first‐order axioms are given from which any first‐order property in graph theory or its negation can be deduced. We show that almost all generalized Steinhaus graphs satisfy these axioms. Thus the first‐order theory of random generalized Steinhaus graphs is identical with the theory of random graphs. Quasi‐random properties of graphs are described by F. R. K. Chung, R. L. Graham, and R. M. Wilson, [“Quasi‐Random Graphs,” Combinatorica, Vol. 9 (1989), pp. 345–362]. We conclude by demonstrating that almost all generalized Steinhaus graphs obey Property 2 and hence all equivalent quasi‐random properties. © 1996 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

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.

Almost all steinhaus graphs have diamete

Almost all steinhaus graphs have diameter 2

✍ Neal Brand 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 300 KB 👁 1 views

## Abstract A Steinhaus graph is a graph with __n__ vertices whose adjacency matrix (__a__~i, j~) satisfies the condition that __a__~i, j~  __a__~a‐‐1, j‐‐1~ + __a__ ~i‐‐1, j~ (mod 2) for each 1 < __i__ < __j__ ≤ __n__. It is clear that a Steinhaus graph is determined by its first row. In [3] Brin

Generalized line graphs

✍ Dragoš Cvetkovic̀; Michael Doob; Slobodan Simic̀ 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 775 KB

## Abstract Generalized line graphs extend the ideas of both line graphs and cocktail party graphs. They were originally motivated by spectral considerations. in this paper several (nonspectral) classical theorems about line graphs are extended to generalized line graphs, including the derivation a

Generalized and/or graphs

✍ Giorgio Levi; Franco Sirovich 📂 Article 📅 1976 🏛 Elsevier Science 🌐 English ⚖ 974 KB

A generalization of AND/OR graphs is introduced as a problem solving model, in which subproblem interdependence in problem reduction can be explicitly accounted for. An ordered-search algorithm is given to fred a solution. The algorithm is proven to be admissible and optimal Examples are given which

Which generalized petersen graphs are ca

Which generalized petersen graphs are cayley graphs?

✍ Roman Nedela; Martin Škoviera 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 572 KB

## Abstract The generalized Petersen graph __GP__ (__n, k__), __n__ ≤ 3, 1 ≥ __k__ < __n__/2 is a cubic graph with vertex‐set {u~j~; i ϵ Z~n~} ∪ {v~j~; i ϵ Z~n~}, and edge‐set {u~i~u~i~, u~i~v~i~, v~i~v~i+k, iϵ~Z~n~}. In the paper we prove that (i) __GP__(__n, k__) is a Cayley graph if and only if

Generalized Pigeonhole Properties of Gra

Generalized Pigeonhole Properties of Graphs and Oriented Graphs

✍ Anthony Bonato; Peter J Cameron; Dejan Delić; Stéphan Thomassé 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 152 KB

A relational structure A satisfies the P(n, k) property if whenever the vertex set of A is partitioned into n nonempty parts, the substructure induced by the union of some k of the parts is isomorphic to A. The P(2, 1) property is just the pigeonhole property, (P), introduced by Cameron, and studied