Geodesic
Strong geodetic problem on complete multipartite graphs
Ars Mathematica Contemporanea, Tome 17 (2019) no. 2, pp. 481-491.

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

The strong geodetic problem is to find the smallest number of vertices such that by fixing one shortest path between each pair, all vertices of the graph are covered. In this paper we study the strong geodetic problem on complete bipartite graphs. Some results for complete multipartite graphs are also derived. Finally, we prove that the strong geodetic problem restricted to (general) bipartite graphs is NP-complete.
DOI : 10.26493/1855-3974.1725.2e5
Keywords: Geodetic problem, strong geodetic problem, (complete) bipartite graphs, (complete) multipartite graphs 
@article{10_26493_1855_3974_1725_2e5,
     author = {Vesna Ir\v{s}i\v{c} and Matja\v{z} Konvalinka},
     title = {Strong geodetic problem on complete multipartite graphs},
     journal = {Ars Mathematica Contemporanea},
     pages = {481--491},
     publisher = {mathdoc},
     volume = {17},
     number = {2},
     year = {2019},
     doi = {10.26493/1855-3974.1725.2e5},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1725.2e5/}
}
TY  - JOUR
AU  - Vesna Iršič
AU  - Matjaž Konvalinka
TI  - Strong geodetic problem on complete multipartite graphs
JO  - Ars Mathematica Contemporanea
PY  - 2019
SP  - 481
EP  - 491
VL  - 17
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1725.2e5/
DO  - 10.26493/1855-3974.1725.2e5
LA  - en
ID  - 10_26493_1855_3974_1725_2e5
ER  - 
%0 Journal Article
%A Vesna Iršič
%A Matjaž Konvalinka
%T Strong geodetic problem on complete multipartite graphs
%J Ars Mathematica Contemporanea
%D 2019
%P 481-491
%V 17
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1725.2e5/
%R 10.26493/1855-3974.1725.2e5
%G en
%F 10_26493_1855_3974_1725_2e5
Vesna Iršič; Matjaž Konvalinka. Strong geodetic problem on complete multipartite graphs. Ars Mathematica Contemporanea, Tome 17 (2019) no. 2, pp. 481-491. doi : 10.26493/1855-3974.1725.2e5. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1725.2e5/

Cité par Sources :