On the strong metric dimension of the strong products of graphs
Let G be a connected graph. A vertex w ∈ V.G/ strongly resolves two vertices u,v ∈ V.G/ if there exists some shortest u-w path containing v or some shortest v-w path containing u. A set S of vertices is a strong resolving set for G if every pair of vertices of G is strongly resolved by some vertex o...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
De Gruyter
2015-01-01
|
| Series: | Open Mathematics |
| Subjects: | |
| Online Access: | https://doi.org/10.1515/math-2015-0007 |
| _version_ | 1831568569809240064 |
|---|---|
| author | Kuziak Dorota Yero Ismael G. Rodríguez-Velázquez Juan A. |
| author_facet | Kuziak Dorota Yero Ismael G. Rodríguez-Velázquez Juan A. |
| author_sort | Kuziak Dorota |
| collection | DOAJ |
| description | Let G be a connected graph. A vertex w ∈ V.G/ strongly resolves two vertices u,v ∈ V.G/ if there
exists some shortest u-w path containing v or some shortest v-w path containing u. A set S of vertices is a strong
resolving set for G if every pair of vertices of G is strongly resolved by some vertex of S. The smallest cardinality
of a strong resolving set for G is called the strong metric dimension of G. It is well known that the problem of
computing this invariant is NP-hard. In this paper we study the problem of finding exact values or sharp bounds for
the strong metric dimension of strong product graphs and express these in terms of invariants of the factor graphs. |
| first_indexed | 2024-12-17T12:17:58Z |
| format | Article |
| id | doaj.art-a421a15e367342918e615af52bfac4f3 |
| institution | Directory Open Access Journal |
| issn | 2391-5455 |
| language | English |
| last_indexed | 2024-12-17T12:17:58Z |
| publishDate | 2015-01-01 |
| publisher | De Gruyter |
| record_format | Article |
| series | Open Mathematics |
| spelling | doaj.art-a421a15e367342918e615af52bfac4f32022-12-21T21:49:06ZengDe GruyterOpen Mathematics2391-54552015-01-0113110.1515/math-2015-0007math-2015-0007On the strong metric dimension of the strong products of graphsKuziak Dorota0Yero Ismael G.1Rodríguez-Velázquez Juan A.2Departament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, Av. Països Catalans 26, 43007 Tarragona, SpainDepartamento de Matemáticas, Escuela Politécnica Superior de Algeciras, Universidad de Cádiz, Av. Ramón Puyol s/n, 11202 Algeciras, SpainDepartament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, Av. Països Catalans 26, 43007 Tarragona, SpainLet G be a connected graph. A vertex w ∈ V.G/ strongly resolves two vertices u,v ∈ V.G/ if there exists some shortest u-w path containing v or some shortest v-w path containing u. A set S of vertices is a strong resolving set for G if every pair of vertices of G is strongly resolved by some vertex of S. The smallest cardinality of a strong resolving set for G is called the strong metric dimension of G. It is well known that the problem of computing this invariant is NP-hard. In this paper we study the problem of finding exact values or sharp bounds for the strong metric dimension of strong product graphs and express these in terms of invariants of the factor graphs.https://doi.org/10.1515/math-2015-0007strong metric dimensionstrong metric basisstrong resolving setstrong product graphs |
| spellingShingle | Kuziak Dorota Yero Ismael G. Rodríguez-Velázquez Juan A. On the strong metric dimension of the strong products of graphs Open Mathematics strong metric dimension strong metric basis strong resolving set strong product graphs |
| title | On the strong metric dimension of the strong products of graphs |
| title_full | On the strong metric dimension of the strong products of graphs |
| title_fullStr | On the strong metric dimension of the strong products of graphs |
| title_full_unstemmed | On the strong metric dimension of the strong products of graphs |
| title_short | On the strong metric dimension of the strong products of graphs |
| title_sort | on the strong metric dimension of the strong products of graphs |
| topic | strong metric dimension strong metric basis strong resolving set strong product graphs |
| url | https://doi.org/10.1515/math-2015-0007 |
| work_keys_str_mv | AT kuziakdorota onthestrongmetricdimensionofthestrongproductsofgraphs AT yeroismaelg onthestrongmetricdimensionofthestrongproductsofgraphs AT rodriguezvelazquezjuana onthestrongmetricdimensionofthestrongproductsofgraphs |