Generalized steinhaus graphs

A generalized Steinhaus graph of order n and type s is a graph with n vertices whose adjacency matrix ( a i,j ) satisfies the relationwhere 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.