On Single-Distance Graphs on the Rational Points in Euclidean Spaces

Bau, Sheng ; Johnson, Peter ; Noble, Matt

Canadian mathematical bulletin, Tome 64 (2021) no. 1, pp. 13-24

Résumé

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)$.

Détail

DOI : 10.4153/S0008439520000181

Mots-clés : Euclidean distance graph, rational points, graph isomorphism, clique number, regular simplex