Contents

-

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 dim(G)=n, if n is the smallest integer such that G can be represented as a unit-distance graph in Rn. 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 n2, there is an arbitrarily large dimension-critical graph G with 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.