The metric dimension of strong product graphs

MaRDI QIDQ2806647zbMATH OpenFDO

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)

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

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)

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.

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

Cited in

(23)

• Bounds on the domination number and the metric dimension of co-normal product of graphs
• On the strong metric dimension of the strong products 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
• The k-metric dimension of corona product graphs
• On Metric Generators of Graphs
• On the metric dimension of circulant and Harary graphs
• Graphs whose mixed metric dimension is equal to their order
• 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 \(\mathbb{Z}_n \times \mathbb{Z}_n \times \mathbb{Z}_n\) is \(\lfloor 3n/2 \rfloor \)
• The metric dimension of strongly regular graphs
• 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)