Assorted Musings on Dimension-critical Graphs

Matt Noble 1
1Department of Mathematics Middle Georgia State University

Abstract

For a finite simple graph \( G \), say \( G \) is of dimension \( n \), and write \( \text{dim}(G) = n \), if \( n \) is the smallest integer such that \( G \) can be represented as a unit-distance graph in \( \mathbb{R}^n \). Define \( G \) to be \emph{dimension-critical} if every proper subgraph of \( G \) has dimension less than \( G \). In this article, we determine exactly which complete multipartite graphs are dimension-critical. It is then shown that for each \( n \geq 2 \), there is an arbitrarily large dimension-critical graph \( G \) with \( \text{dim}(G) = n \). We close with a few observations and questions that may aid in future work.

Keywords: graph dimension, unit-distance graph embeddings, edge-criticality, complete multipartite graphs.