For positive integers n and d > 0, let $G(\mathbb {Q}^n,\; d)$ denote the graph whose vertices are the set of rational points $\mathbb {Q}^n$, with $u,v \in \mathbb {Q}^n$ being adjacent if and only if the Euclidean distance between u and v is equal to d. Such a graph is deemed “non-trivial” if d is actually realized as a distance between points of $\mathbb {Q}^n$. In this paper, we show that a space $\mathbb {Q}^n$ has the property that all pairs of non-trivial distance graphs $G(\mathbb {Q}^n,\; d_1)$ and $G(\mathbb {Q}^n,\; d_2)$ are isomorphic if and only if n is equal to 1, 2, or a multiple of 4. Along the way, we make a number of observations concerning the clique number of $G(\mathbb {Q}^n,\; d)$.

We give a new, simplified and detailed account of the correspondence between levels of the Sherali–Adams relaxation of graph isomorphism and levels of pebble-game equivalence with counting (higher-dimensional Weisfeiler–Lehman colour refinement). The correspondence between basic colour refinement and fractional isomorphism, due to Tinhofer [22; 23] and Ramana, Scheinerman and Ullman [17], is re-interpreted as the base level of Sherali–Adams and generalised to higher levels in this sense by Atserias and Maneva [1] and Malkin [14], who prove that the two resulting hierarchies interleave. In carrying this analysis further, we here give (a) a precise characterisation of the level k Sherali–Adams relaxation in terms of a modified counting pebble game; (b) a variant of the Sherali–Adams levels that precisely match the k-pebble counting game; (c) a proof that the interleaving between these two hierarchies is strict. We also investigate the variation based on boolean arithmetic instead of real/rational arithmetic and obtain analogous correspondences and separations for plain k-pebble equivalence (without counting). Our results are driven by considerably simplified accounts of the underlying combinatorics and linear algebra.

We introduce a type of isomorphism among strategic games that we call localisomorphism. Local isomorphisms is a weaker version of the notions of strongand weak game isomorphism introduced in [J. Gabarro, A. Garcia and M. Serna,Theor. Comput. Sci. 412 (2011) 6675–6695]. In a localisomorphism it is required to preserve, for any player, the player’s preferences on thesets of strategy profiles that differ only in the action selected by this player. We showthat the game isomorphism problem for local isomorphism is equivalent to the same problemfor strong or weak isomorphism for strategic games given in: general, extensive andformula general form. As a consequence of the results in [J. Gabarro, A. Garcia and M.Serna, Theor. Comput. Sci. 412 (2011) 6675–6695] thisimplies that local isomorphism problem for strategic games is equivalent to (a) thecircuit isomorphism problem for games given in general form, (b) the boolean formulaisomorphism problem for formula games in general form, and (c) the graph isomorphismproblem for games given in explicit form.

The isomorphism problem for circulant graphs (Cayley graphs over the cyclic group) which has been open since 1967 is completely solved in this paper. The main result of the paper gives an efficient isomorphism criterion for circulant graphs of arbitrary order. This result also solves an isomorphism problem for colored circulant graphs and some classes of cyclic codes.