Abstract#R##N##R##N#A generalized Steinhaus graph of order n and type s is a graph with n vertices whose adjacency matrix (ai,j) satisfies the relation #R##N##R##N##R##N##R##N##R##N##R##N##R##N#where 2 ≦i≦n−1, i + s(i − 1 ≦ j ≦ n, cr,i,j ϵ {0,1} for all 0 ≦ r ≦ s(i) −1 and cs(i)−1,i,j = 1. The values of s(i) and cr,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.
['Neal Brand', 'Margaret Morton']
Generalized Steinhaus graphs