A cubic lattice graph is defined
to be a graph G, whose vertices are the ordered triplets on n symbols, such that two
vertices are adjacent if and only if they have two coordinates in common. If n2(x)
denotes the number of vertices y, which are at distance 2 from x and A(G) denotes
the adjacency matrix of G, then G has the following properties: (P1) the number of
vertices is n3. (P2) G is connected and regular. (P3) n2(x) = 3(n − 1)2. (P4) the
distinct eigenvalues of A(G) are −3, n − 3, 2n − 3, 3(n − 1). It is shown here that if
n > 7, any graph G (with no loops and multiple edges) having the properties
(P1)–(P4) must be a cubic lattice graph. An alternative characterization of cubic
lattice graphs has been given by the author (J. Comb. Theory, Vol. 3, No. 4,
December 1967, 386–401).
