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}$. Surprisingly, the realizability of an order on a disconnected graph is not determined by its restrictions to the connected components. We also study realizability on the real line: we characterize which disjoint unions of two cycles are realizable, and estimate the largest number of edges an $n$-vertex graph can have while all of its edge-orders remain realizable on the line. In general dimension, we show that the largest number of edges of an $n$-vertex graph all of whose edge-orders are realizable in $\mathbb{R}^d$ is $dn+O\!\left(dn/\ln(dn)\right)$.

Disclosure

“lowship Program. The second author received support from UNAM DGAPA- PASPA to work on this topic during a sabbatical stay at the Instituto de Matemáticas, Unidad Juriquilla, UNAM. The authors acknowledge the use of Claude, developed by Anthropic, to assist with the drafting and reorganization of parts of the manuscript, including the figures, to improve the clarity and presentation of the exposition, and to help implement simple algorithms used during the exploratory stages of the”

PDF page 20

Classification

Drafting limited passages

Multiplier

5

Verified

2026-08-23T05:18:10.657013Z

Structural counts