General d-position sets

Sandi Klavžar, Douglas F. Rall, Ismael Gonzalez Yero

Abstract


The general d-position number gpd(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 gpd(G) with respect to the suitable values of d. We show that the decision problem concerning finding gpd(G) is NP-complete for any value of d. The value of gpd(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 gpd(G) is infinite whenever G is an infinite graph and d is a finite integer.


Keywords


General d-position sets, dissociation sets, strong resolving graphs, computational complexity, infinite graphs

Full Text:

MANUSCRIPT


DOI: https://doi.org/10.26493/1855-3974.2384.77d

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications