Different-Distance Sets in a Graph

Document Type : Original paper

Authors

1 Wingate University

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

3 Clemson University

4 Erasmus Universiteit

Abstract

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-istance numbers of paths, cycles, Cartesian products of bipartite graphs, and Cartesian products of complete graphs. We conclude with some open problems and questions.

Keywords

Main Subjects

References

[1] G. Chartrand, L. Eroh, M.A. Johnson, and O.R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000), no. 1-3, 99–113.
[2] G. Chartrand and P. Zhang, The theory and application of resolvability in graphs, Congr. Numer. 160 (2003), 47–68.
[3] R. Hammack, W. Imrich, and S. Klavzar, Handbook of graph products, CRC Press Boca Raton FL, 2011.
[4] H.M. Mulder, The interval function of a graph, Math. Centre Tracts 132, Amsterdam, 1980.
[5] P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975), 549–559.
 
Communications in Combinatorics and Optimization
Volume 4, Issue 2
Special issue in honour of Prof. Lutz Volkmann
December 2019
Pages 151-171

Files

Share

How to cite

Statistics