ORTHOGONAL LATIN SQUARE GRAPHS

An orthogonal latin square graph (OLSG) is one in which the vertices are latin squares of the same order and on the same symbols, and two vertices are adjacent if and only if the latin squares are orthogonal. If G is an arbitrary finite graph, we say that G is realizable as an OLSG if there is an OLSG isomorphic to G. The spectrum of G [Spec(G)] is defined as the set of all integers n that there is a realization of G by latin squares of order n. The two basic theorems proved here are (1) every graph is realizable and (2) for any graph G, Spec G contains all but a finite set of integers. A number of examples are given that point to a number of wide open questions. An example of such a question is how to classify the graphs for which a given n lies in the spectrum. Copyright © 1979 Wiley Periodicals, Inc., A Wiley Company