The least Euclidean distortion constant of a distance-regular graph

2021/09/20 by Sebastian M. Cioabă, Cioabă, Sebastian M., Himanshu Gupta +5
Computer Science · Engineering · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Interconnection Networks and Systems #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2109.09708

openalex publication_date 2021/09/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In 2008, Vallentin made a conjecture involving the least distortion of an embedding of a distance-regular graph into Euclidean space. Vallentin's conjecture implies that for a least distortion Euclidean embedding of a distance-regular graph of diameter d, the most contracted pairs of vertices are those at distance d. In this paper, we confirm Vallentin's conjecture for several families of distance-regular graphs. We also provide counterexamples to this conjecture, where the largest contraction occurs between pairs of vertices at distance d-1. We suggest three alternative conjectures and prove them for several families of distance-regular graphs.

Related

• Distance-regular graph with large a1 or c2
• The metric dimension of small distance-regular and strongly regular graphs
• There are only finitely many distance-regular graphs with valency k at least three, fixed ratio k2/k and large diameter
• Embedding Euclidean Distance Graphs in ℝⁿ and ℚⁿ
• A relationship between the diameter and the intersection number c2 for a distance-regular graph