Geodesic
General d-position sets
Ars Mathematica Contemporanea, Tome 21 (2021) no. 1, article no. 03, 12 p.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

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.
DOI : 10.26493/1855-3974.2384.77d
Keywords: General d-position sets, dissociation sets, strong resolving graphs, computational complexity, infinite graphs 
@article{10_26493_1855_3974_2384_77d,
     author = {Sandi Klav\v{z}ar and Douglas F. Rall and Ismael G. Yero},
     title = {General d-position sets},
     journal = {Ars Mathematica Contemporanea},
     eid = {03},
     publisher = {mathdoc},
     volume = {21},
     number = {1},
     year = {2021},
     doi = {10.26493/1855-3974.2384.77d},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2384.77d/}
}
TY  - JOUR
AU  - Sandi Klavžar
AU  - Douglas F. Rall
AU  - Ismael G. Yero
TI  - General d-position sets
JO  - Ars Mathematica Contemporanea
PY  - 2021
VL  - 21
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2384.77d/
DO  - 10.26493/1855-3974.2384.77d
LA  - en
ID  - 10_26493_1855_3974_2384_77d
ER  - 
%0 Journal Article
%A Sandi Klavžar
%A Douglas F. Rall
%A Ismael G. Yero
%T General d-position sets
%J Ars Mathematica Contemporanea
%D 2021
%V 21
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2384.77d/
%R 10.26493/1855-3974.2384.77d
%G en
%F 10_26493_1855_3974_2384_77d
Sandi Klavžar; Douglas F. Rall; Ismael G. Yero. General d-position sets. Ars Mathematica Contemporanea, Tome 21 (2021) no. 1, article  no. 03, 12 p. doi : 10.26493/1855-3974.2384.77d. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2384.77d/

Cité par Sources :