Distance graphs on R n with 1-norm

Suppose S is a subset of a metric space X with metric d. For each subset D⊆{d(x,y):x,y∈S,x≠y}, the distance graph G(S,D) is the graph with vertex set S and edge set E(S,D)={xy:x,y∈S,d(x,y)∈D}. The current paper studies distance graphs on the n-space R ₁ ⁿ with 1-norm. In particular, most attention is paid to the subset Z ₁ ⁿ of all lattice points of R ₁ ⁿ . The results obtained include the degrees of vertices, components, and chromatic numbers of these graphs. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. Supported in part by the National Science Council under grant NSC-94-2115-M-002-015. Taida Institue for Mathematical Sciences, National Taiwan University, Taipei 10617, Taiwan. National Center for Theoretical Sciences, Taipei Office.