no. 14 · Friday 13 November 2026
Disconnected graphs and extremal bounds for realizable distance orders
Abstract
Let $G$ be a graph together with a total order $\prec$ on its edges. We say that $\prec$ is realizable in $\mathbb{R}^d$ if there is a placement of the vertices of $G$ in $\mathbb{R}^d$ such that the Euclidean lengths of the edges induce exactly the order $\prec$. Almendra-Hernández and Martínez-Sandoval proved that every total order on the edges of the complete graph $K_n$ is realizable in $\mathbb{R}^{n-2}$. We show that the same is not true for the disjoint union of two complete graphs: for every $n\geq 3$ there is a total order on the edges of $K_n\sqcup K_n$ that is not realizable in $\mathbb{R}^{n-2}$, but is in $\mathbb{R}^{n-1}$. Thus, the realizability of an order on a disconnected graph is not determined by its restrictions to the connected components. We also study the extremal problem of maximizing the number of edges of an $n$-vertex graph all of whose edge-orders are realizable in $\mathbb{R}^d$, and show that for every fixed $d$ this maximum is $dn+o(n)$, with explicit bounds on the error term. On the real line we sharpen these bounds and show that a disjoint union of two cycles is realizable in $\mathbb{R}$ unless both cycles are triangles.
- comments
- v3: added references (Bilu-Linial 2005; Shepard 1962, Guttman 1968, Lingoes 1971) and corrected attributions; improved lower bound for R(K_n) via Maehara (1991), giving R(K_5)=3 and R(K_6)=4; added remark on arboricity. 23 pages, 3 figures
- fields
- Combinatorics