Distance-k 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.
See also
Distance Graph, Euclidean Distance Graph, Graph Distance, Graph Distance GraphExplore with Wolfram|Alpha
More things to try:
Cite this as:
Weisstein, Eric W. "Distance-k Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Distance-kGraph.html