Embedding Euclidean distance graphs in R^n and Q^n

DOI10.1007/S00010-022-00895-1MaRDI QIDQ2172834zbMATH OpenOpenAlexWikidataFDO

Authors Matt Noble

Publication date 16 September 2022

Published in Aequationes Mathematicae (Search for Journal in Brave)

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

zbMATH Keywords

euclidean distance graphgraph dimensiongraph embeddingrational points

Mathematics Subject Classification ID

Distance in graphs (05C12) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: For $SsubseteqmathbbR$, positive integer $n$, and $d>0$, let $G(S^n,d)$ be the graph whose vertex set is $S^n$ where any two vertices are adjacent if and only if they are Euclidean distance $d$ apart. The primary question we will consider in our work is as follows. Given $n$ and distance $d$ actually realized as a distance between points of the rational space $mathbb{Q}^n$, does there exist a finite graph $G$ that appears as a subgraph of $G(mathbb{Q}^n,d)$ but not as a subgraph of $G(mathbb{R}^{n-1},1)$? We answer this question affirmatively for $nleq5$, and along the way, resolve a few related questions as well.

Recommendations

• On single-distance graphs on the rational points in Euclidean spaces
• Euclidean Distance Graphs on the Rational Points
• On distance graphs in rational spaces
• Note on induced subgraphs of the unit distance graph \(E^ n\)
• A characterization in \(\mathbb{Z}^ n\) of finite unit-distance graphs in \(\mathbb{R}^ n\)

Cites work

• Computing small unit-distance graphs with chromatic number 5
• scientific article; zbMATH DE number 3730165 (Why is no real title available?)
• scientific article; zbMATH DE number 3065066 (Why is no real title available?)
• On single-distance graphs on the rational points in Euclidean spaces
• On the dimension of a graph
• On the Euclidean dimension of a complete multipartite graph
• Regular Simplices and Quadratic Forms
• The chromatic number of the plane is at least 5
• The chromatic number of the plane is at least 5: a new proof
• The Mathematical Coloring Book
• Triangles with Vertices on Lattice Points
• Two notions of unit distance graphs

Cited in

(9)

• A divide-and-conquer strategy for embedding a distance-net point set into \(E^ n\) and its application
• On complexity of multidistance graph recognition in \(\mathbb{R}^1\)
• Euclidean Distance Graphs on the Rational Points
• On the distance and multidistance graph embeddability problem
• scientific article; zbMATH DE number 1045540 (Why is no real title available?)
• scientific article; zbMATH DE number 1452726 (Why is no real title available?)
• scientific article; zbMATH DE number 1890143 (Why is no real title available?)
• On single-distance graphs on the rational points in Euclidean spaces
• On distance graphs in rational spaces

This page was built for publication: Embedding Euclidean distance graphs in \(\mathbb{R}^n\) and \(\mathbb{Q}^n\)

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