The least Euclidean distortion constant of a distance-regular graph

DOI10.1016/J.DAM.2022.10.014zbMATH Open1504.05077arXiv2109.09708OpenAlexW3200406367MaRDI QIDQ2104939FDOQ2104939

Authors: Sebastian Cioaba, Himanshu Gupta, Ferdinand Ihringer, Hirotake Kurihara 

Publication date: 8 December 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/2109.09708

Recommendations

• scientific article; zbMATH DE number 782048
• Optimal distortion embeddings of distance regular graphs into Euclidean spaces
• The equidistant dimension of graphs
• On Euclidean distance matrices of graphs
• Distance regularity in direct-product graphs
• scientific article; zbMATH DE number 681028
• On the Cheeger constant for distance-regular graphs
• Diameter bounds for geometric distance-regular graphs
• On the least distance eigenvalue of a graph
• Some elementary inequalities for distance-regular graphs

zbMATH Keywords

eigenvalues of graphsdistance-regular graphsEuclidean embeddingodd graphsGrassmann graphsgraphs with classical parametersHermitian forms graphsleast distortion

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Association schemes, strongly regular graphs (05E30) Distance in graphs (05C12)

Cites Work

• Title not available (Why is that?)
• The geometry of graphs and some of its algorithmic applications
• Title not available (Why is that?)
• A partially ordered set and q-Krawtchouk polynomials
• On Lipschitz embedding of finite metric spaces in Hilbert space
• On the nonexistence of uniform homeomorphisms between \(L^ p\)-spaces
• The Euclidean distortion of generalized polygons
• Least-distortion Euclidean embeddings of graphs: Products of cycles and expanders
• Optimal distortion embeddings of distance regular graphs into Euclidean spaces
• Hermitian rank distance codes
• The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters
• \(L^{p}\)-distortion and \(p\)-spectral gap of finite graphs

Cited In (2)

• Optimal distortion embeddings of distance regular graphs into Euclidean spaces
• Least distortion Euclidean embeddings of flat tori

This page was built for publication: The least Euclidean distortion constant of a distance-regular graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2104939)