k-distance graph

The term "distance-k graph" (or k-distance graph) refers to a graph constructed on a given vertex set where edges are constructed iff two vertices are at a distance exactly k from each other. A number of differet types of distances are commonly considered, including graph distance (giving a graph distance graph) and Euclidean distance (when the embedding of the vertex set is given, giving a Euclidean distance graph). The Grabarchuk graph is a Euclidean distance-3 graph on the vertex set of the 4×4×4 grid graph. Generalizations allowing the distance to be one of several possible values are also considered. Such graphs may generally be termed distance graphs.

distance graph | Euclidean distance graph | graph distance | graph distance graph