Strong geodetic problem on Cartesian products of graphs

Iršič, Vesna; Klavžar, Sandi

doi:10.1051/ro/2018003

Iršič, Vesna ¹ ; Klavžar, Sandi ¹

RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 1, pp. 205-216.

Résumé

The strong geodetic problem is a recent variation of the geodetic problem. For a graph $G$ , its strong geodetic number sg $(G)$ is the cardinality of a smallest vertex subset $S$ , such that each vertex of $G$ lies on a fixed shortest path between a pair of vertices from $S$ . In this paper, the strong geodetic problem is studied on the Cartesian product of graphs. A general upper bound for sg $(G □ H)$ is determined, as well as exact values for $K_{m} □ K_{n}, K_{1, k} □ P_{l}$ , and prisms over □ K, and prisms over $K_{n} - e$ . Connections between the strong geodetic number of a graph and its subgraphs are also discussed.–e. Connections between the strong geodetic number of a graph and its subgraphs are also discussed.

MR Zbl

DOI : 10.1051/ro/2018003

Classification : 05C12, 05C70, 68Q17, 68Q17
Mots clés : Geodetic problem, strong geodetic problem, isometric path problem, Cartesian product, subgraph

Affiliations des auteurs :

Iršič, Vesna ¹ ; Klavžar, Sandi ¹

@article{RO_2018__52_1_205_0,
     author = {Ir\v{s}i\v{c}, Vesna and Klav\v{z}ar, Sandi},
     title = {Strong geodetic problem on {Cartesian} products of graphs},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {205--216},
     publisher = {EDP-Sciences},
     volume = {52},
     number = {1},
     year = {2018},
     doi = {10.1051/ro/2018003},
     mrnumber = {3812477},
     zbl = {1392.05033},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2018003/}
}

TY  - JOUR
AU  - Iršič, Vesna
AU  - Klavžar, Sandi
TI  - Strong geodetic problem on Cartesian products of graphs
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2018
SP  - 205
EP  - 216
VL  - 52
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2018003/
DO  - 10.1051/ro/2018003
LA  - en
ID  - RO_2018__52_1_205_0
ER  -

%0 Journal Article
%A Iršič, Vesna
%A Klavžar, Sandi
%T Strong geodetic problem on Cartesian products of graphs
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2018
%P 205-216
%V 52
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2018003/
%R 10.1051/ro/2018003
%G en
%F RO_2018__52_1_205_0

Iršič, Vesna; Klavžar, Sandi. Strong geodetic problem on Cartesian products of graphs. RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 1, pp. 205-216. doi : 10.1051/ro/2018003. http://www.numdam.org/articles/10.1051/ro/2018003/

Bibliographie
Cité par

[1] H.A. Ahangar, S. Kosari, S.M. Sheikholeslami and L. Volkmann, Graphs with large geodetic number. Filomat 29 (2015) 1361–1368. | DOI | MR | Zbl

[2] B. Brešar, M. Kovše and A. Tepeh, Geodetic sets in graphs, in Structural Analysis of Complex Networks. Birkhäuser/Springer, New York (2011) 197–218. | DOI | MR | Zbl

[3] C.C. Centeno, L.D. Penso, D. Rautenbach and V.G. Pereira De Sá, Geodetic number versus hull number in P₃-convexity. SIAM J. Discrete Math. 27 (2013) 717–731. | DOI | MR | Zbl

[4] G. Chartrand and P. Zhang, Extreme geodesic graphs. Czechoslov. Math. J. 52 (2002) 771–780. | DOI | MR | Zbl

[5] T. Ekim and A. Erey, Block decomposition approach to compute a minimum geodetic set. RAIRO: OR 48 (2014) 497–507. | DOI | Numdam | MR | Zbl

[6] D.C. Fisher and S.L. Fitzpatrick, The isometric path number of a graph. J. Combin. Math. Combin. Comput. 38 (2001) 97–110. | MR | Zbl

[7] S.L. Fitzpatrick, Isometric path number of the Cartesian product of paths. Congr. Numer. 137 (1999) 109–119. | MR | Zbl

[8] A.S. Fraenkel and F. Harary, Geodetic contraction games on graphs. Int. J. Game Theory 18 (1989) 327–338. | DOI | MR | Zbl

[9] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, 2nd edn. CRC Press Inc., Boca Raton, FL (2011). | DOI | MR | Zbl

[10] F. Harary, E. Loukakis and C. Tsouros, The geodetic number of a graph. Math. Comput. Model. 17 (1993) 89–95. | DOI | MR | Zbl

[11] V. Iršič, Strong geodetic number of complete bipartite graphs and of graphs with specified diameter. To appear in: Graphs Comb. (2018). | MR | Zbl

[12] T. Jiang, I. Pelayo and D. Pritikin, Geodesic convexity and Cartesian products in graphs. Available at jupiter.math.nctu.edu.tw/~weng/references/others/graph_product_2004.pdf (2018).

[13] S. Klavžar and P. Manuel, Strong Geodetic Problem in Grid-Like Architectures. To appear in: | MR | Zbl

[14] C. Lu, The geodetic numbers of graphs and digraphs. Sci. China Ser. A 50 (2007) 1163–1172. | MR | Zbl

[15] P. Manuel, S. Klavžar, A. Xavier, A. Arokiaraj and E. Thomas, Strong geodetic problem in networks. Preprint (2017). | arXiv | MR

[16] P. Manuel, S. Klavžar, A. Xavier, A. Arokiaraj and E. Thomas, Strong edge geodetic problem in networks. Open Math. 15 (2017) 1225–1235. | MR | Zbl

[17] J.-J. Pan and G.J. Chang, Isometric path numbers of graphs. Discrete Math. 306 (2006) 2091–2096. | MR | Zbl

[18] I.M. Pelayo, Geodesic Convexity in Graphs. Springer Briefs in Mathematics. Springer, New York (2013). | MR | Zbl

[19] J.A. Soloff, R.A. Márquez and L.M. Friedler, Products of geodesic graphs and the geodetic number of products. Discuss. Math. Graph Theory 35 (2015) 35–42. | MR | Zbl

Cité par Sources :