Disconnected graphs and extremal bounds for realizable distance orders

Abstract

Let G be a graph together with a total order ≺ on its edges. We say that ≺ is realizable in ℝ^d if there is a placement of the vertices of G in ℝ^d such that the Euclidean lengths of the edges induce exactly the order ≺. Almendra-Hernández and Martínez-Sandoval proved that every total order on the edges of the complete graph K_n is realizable in ℝⁿ⁻². We show that the same is not true for the disjoint union of two complete graphs: for every n≥ 3 there is a total order on the edges of K_nsqcup K_n that is not realizable in ℝⁿ⁻², but is in ℝⁿ⁻¹. 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 ℝ^d is dn+O (dn/ln(dn)).

Neighbourhood second Zagreb matrix of graphs: spectral radius bounds and extremal graphs
Subhendu Chakraborty, Priti Prasanna Mondal
arXiv4 Nov 2026PreprintCC BY 4.0Full textAnalysis & PDEs Combinatorics & discrete mathematicsarXiv
Generalized Spectral Closedness and the Nonexistence of Walk-Realizable Supporters for Split Graphs
Yanyang Li
arXiv29 Aug 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
On the existence of F-irregular graphs for disconnected graphs F
Tatiana Dovzhenok
arXiv13 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Quasi-isometries between graphs of totally disconnected locally compact groups
Sebastian Giersbach
arXiv12 Oct 2026PreprintarXiv licenceFull textAlgebra & number theoryarXiv
Sharp margin-based generalization bounds for realizable SVM
Steve Hanneke, Aryeh Kontorovich
arXiv15 Sep 2026PreprintCC BY 4.0Full textStatisticsarXiv

Cite

BibTeX RIS

BibTeX

@misc{maldonado2026disconnected,
  title = {{Disconnected graphs and extremal bounds for realizable distance orders}},
  author = {Gerardo L. Maldonado and Leonardo Martínez-Sandoval and Miguel Raggi and Edgardo Roldán-Pensado},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2608.15853},
  eprint = {2608.15853},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.15853},
}

RIS

TY  - UNPB
TI  - Disconnected graphs and extremal bounds for realizable distance orders
AU  - Gerardo L. Maldonado
AU  - Leonardo Martínez-Sandoval
AU  - Miguel Raggi
AU  - Edgardo Roldán-Pensado
PY  - 2026
DA  - 2026/09/19
PB  - arXiv
DO  - 10.48550/arxiv.2608.15853
UR  - https://arxiv.org/abs/2608.15853
AB  - Let G be a graph together with a total order ≺ on its edges. We say that ≺ is realizable in ℝ^d if there is a placement of the vertices of G in ℝ^d such that the Euclidean lengths of the edges induce exactly the order ≺. Almendra-Hernández and Martínez-Sandoval proved that every total order on the edges of the complete graph K_n is realizable in ℝ^n−2. We show that the same is not true for the disjoint union of two complete graphs: for every n≥ 3 there is a total order on the edges of K_nsqcup K_n that is not realizable in ℝ^n−2, but is in ℝ^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 ℝ^d is dn+O (dn/ln(dn)).
ER  -

Abstract

Related

Cite