Different-Distance Sets in a Graph

Document Type : Original paper


1 Wingate University

2 Department of Mathematics, University of Johannesburg, Auckland Park, South Africa

3 Clemson University

4 Erasmus Universiteit


A set of vertices $S$ in a connected graph $G$ is a different-distance set if, for any vertex $w$ outside $S$, no two vertices in $S$ have the same distance to $w$.
The lower and upper different-distance number of a graph are the order of a smallest, respectively largest, maximal different-distance set.
We prove that a different-distance set induces either a special type of path or an independent set. We present properties of different-distance sets, and consider the different-distance numbers of paths, cycles, Cartesian products of bipartite graphs, and Cartesian products of complete graphs. We conclude with some open problems and questions.


Main Subjects