The metric dimension of strong product graphs

zbMATH Open1349.05096arXiv1305.0363MaRDI QIDQ2806647FDOQ2806647

Authors: Dorota Kuziak, Ismael G. Yero, Juan A. Rodríguez-Velázquez, Jose M. Sigarreta 

Publication date: 18 May 2016

Published in: Carpathian Journal of Mathematics (Search for Journal in Brave)

Abstract: For an ordered subset $S=s_1,s_2,dots{s}_k$ of vertices and a vertex $u$ in a connected graph $G$, the metric representation of $u$ with respect to $S$ is the ordered $k$-tuple $r(u|S)=(d_G(v,s_1),d_G(v,s_2),dots,$ $d_G(v,s_k))$, where $d_G(x,y)$ represents the distance between the vertices $x$ and $y$. The set $S$ is a metric generator for $G$ if every two different vertices of $G$ have distinct metric representations. A minimum metric generator is called a metric basis for $G$ and its cardinality, $dim(G)$, the metric dimension of $G$. It is well known that the problem of finding the metric dimension of a graph is NP-Hard. In this paper we obtain closed formulae and tight bounds for the metric dimension of strong product graphs.

Full work available at URL: https://arxiv.org/abs/1305.0363

Recommendations

• On the strong metric dimension of the strong products of graphs
• On the strong metric dimension of Cartesian and direct products of graphs
• On the strong metric dimension of product graphs
• Strong metric dimension of rooted product graphs
• Computing the metric dimension of a graph from primary subgraphs

zbMATH Keywords

metric dimensionresolving setmetric generatormetric basisstrong product graph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distance in graphs (05C12) Paths and cycles (05C38) Connectivity (05C40) Graph operations (line graphs, products, etc.) (05C76)

Cited In (23)

• On the strong metric dimension of the strong products of graphs
• Bounds on the domination number and the metric dimension of co-normal product of graphs
• The partition dimension of strong product graphs and Cartesian product graphs
• On the strong partition dimension of graphs
• Resolvability and convexity properties in the Sierpiński product of graphs
• Strong resolving partitions for strong product graphs and Cartesian product graphs
• The local metric dimension of amalgamation of graphs
• On the strong metric dimension of Cartesian and direct products of graphs
• On metric dimensions of symmetric graphs obtained by rooted product
• On the metric representation of the vertices of a graph
• On Metric Generators of Graphs
• Graphs whose mixed metric dimension is equal to their order
• The \(k\)-metric dimension of corona product graphs
• On the metric dimension of circulant and Harary graphs
• Complexity and equivalency of multiset dimension and ID-colorings
• Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
• Optimal strategies for the static black-peg AB game with two and three pegs
• Strong metric dimension of rooted product graphs
• The metric dimension of strongly regular graphs
• The metric dimension of \(\mathbb{Z}_n \times \mathbb{Z}_n \times \mathbb{Z}_n\) is \(\lfloor 3n/2 \rfloor \)
• Computing the metric dimension of a graph from primary subgraphs
• Computing the metric dimension of the categorial product of some graphs
• The local metric dimension of strong product graphs

This page was built for publication: The metric dimension of strong product graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2806647)