Sandi Klavžar: General d-position sets

Date of publication: 18. 1. 2021
Discrete mathematics seminar
ID: 997 6207 6197 – Password: 144896

Tuesday, January 19th at 10.15

Join Zoom Meeting

Meeting ID: 997 6207 6197
Passcode: 144896
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. In this talk, we will first give some results concerning the monotonic behavior of gpd(G) with respect to the suitable values of d. We will show that the decision problem concerning finding gpd(G) is NP-complete for any value of d. Then we have a look to infinite graphs. A structural characterization of general d-position sets will be given. Some relationships with other topics including strong resolving graphs and dissociation sets will also be presented.

Based on a joint work with Douglas F. Rall and Ismael G. Yero.