General d-position sets

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.