Sandi Klavžar: General d-position sets
Date of publication: 18. 1. 2021
Discrete mathematics seminar
Tuesday
19
January
Time:
10:15
Location:
Zoom
ID: 997 6207 6197
–
Password: 144896
Tuesday, January 19th at 10.15
Join Zoom Meeting
https://uni-lj-si.zoom.us/j/99762076197?pwd=WGZXY29URFJ2cXZ0SkVLYWNGN0Z5dz09
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.
Based on a joint work with Douglas F. Rall and Ismael G. Yero.
