TY - JOUR
T1 - Connectedness of Unit Distance Subgraphs Induced by Closed Convex Sets
AU - Janssen, Remie
AU - van Steijn, Leonie
PY - 2022
Y1 - 2022
N2 - The unit distance graph G1Rd is the infinite graph whose nodes are points in Rd, with an edge between two points if the Euclidean distance between these points is 1. The 2-dimensional version G1R2 of this graph is typically studied for its chromatic number, as in the Hadwiger-Nelson problem. However, other properties of unit distance graphs are rarely studied. Here, we consider the restriction of G1Rd to closed convex subsets X of Rd. We show that the graph G1Rd[X] is connected precisely when the radius of r(X) of X is equal to 0, or when r(X) ≥ 1 and the affine dimension of X is at least 2. For hyperrectangles, we give bounds for the graph diameter in the critical case that the radius is exactly 1.
AB - The unit distance graph G1Rd is the infinite graph whose nodes are points in Rd, with an edge between two points if the Euclidean distance between these points is 1. The 2-dimensional version G1R2 of this graph is typically studied for its chromatic number, as in the Hadwiger-Nelson problem. However, other properties of unit distance graphs are rarely studied. Here, we consider the restriction of G1Rd to closed convex subsets X of Rd. We show that the graph G1Rd[X] is connected precisely when the radius of r(X) of X is equal to 0, or when r(X) ≥ 1 and the affine dimension of X is at least 2. For hyperrectangles, we give bounds for the graph diameter in the critical case that the radius is exactly 1.
UR - http://www.scopus.com/inward/record.url?scp=85129374329&partnerID=8YFLogxK
U2 - 10.20429/tag.2022.090102
DO - 10.20429/tag.2022.090102
M3 - Article
AN - SCOPUS:85129374329
SN - 2470-9859
VL - 9
JO - Theory and Applications of Graphs
JF - Theory and Applications of Graphs
IS - 1
M1 - 2
ER -