General d-position sets - Klavžar, Sandi (Ars mathematica contemporanea, 2021)
The general ?$d$?-position number ?${\rm 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 ?${\rm gp}_d(G)$? with respect to the suitable values of ?$d$?. We show that the decision problem concerning finding ?${\rm gp}_d(G)$? is NP-complete for any value of ?$d$?. The value of ?${\rm 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 ?${\rm gp}_d(G)$? is infinite whenever ?$G$? is an infinite graph and ?$d$? is a finite integer.
Keywords: disociacijske množice; grafi; krepki solventni graf; množice; računska zahtevnost