General d-position sets
Sandi Klavžar, Douglas F. Rall, Ismael G. Yero
Abstract
The general d -position number gp d ( G ) of a graph G is the cardinality of a largest set S for which no three distinct vertices from S lie on a common geodesic of length at most d . This new graph parameter generalizes the well studied general position number. We first give some results concerning the monotonic behavior of gp d ( G ) with respect to the suitable values of d . We show that the decision problem concerning finding gp d ( G ) is NP-complete for any value of d . The value of gp d ( G ) when G is a path or a cycle is computed and a structural characterization of general d -position sets is shown. Moreover, we present some relationships with other topics including strong resolving graphs and dissociation sets. We finish our exposition by proving that gp d ( G ) is infinite whenever G is an infinite graph and d is a finite integer.