The simultaneous metric dimension of graph families

DOI10.1016/J.DAM.2015.06.012zbMATH Open1327.05186arXiv1501.00565OpenAlexW118899274WikidataQ57974183 ScholiaQ57974183MaRDI QIDQ897612FDOQ897612

Authors: Yunior Ramírez-Cruz, Ortrud R. Oellermann, Juan A. Rodríguez-Velázquez 

Publication date: 7 December 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: A vertex $vinV$ is said to resolve two vertices $x$ and $y$ if $d_G(v,x)e{d}_G(v,y)$. A set $SsubsetV$ is said to be a metric generator for $G$ if any pair of vertices of $G$ is resolved by some element of $S$. A minimum metric generator is called a metric basis, and its cardinality, $dim(G)$, the emph{metric dimension} of $G$. A set $SsubseteqV$ is said to be a simultaneous metric generator for a graph family $calG=G_1,G_2,ldots,G_k$, defined on a common (labeled) vertex set, if it is a metric generator for every graph of the family. A minimum cardinality simultaneous metric generator is called a simultaneous metric basis, and its cardinality the simultaneous metric dimension of $calG$. We obtain sharp bounds for this invariants for general families of graphs and calculate closed formulae or tight bounds for the simultaneous metric dimension of several specific graph families. For a given graph $G$ we describe a process for obtaining a lower bound on the maximum number of graphs in a family containing $G$ that has simultaneous metric dimension equal to $dim(G)$. It is shown that the problem of finding the simultaneous metric dimension of families of trees is $NP$-hard. Sharp upper bounds for the simultaneous metric dimension of trees are established. The problem of finding this invariant for families of trees that can be obtained from an initial tree by a sequence of successive edge-exchanges is considered. For such families of trees sharp upper and lower bounds for the simultaneous metric dimension are established.

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

Recommendations

• Simultaneous resolvability in graph families
• The simultaneous strong metric dimension of graph families
• The simultaneous local metric dimension of graph families
• The simultaneous metric dimension of families composed by lexicographic product graphs
• Simultaneous resolvability in families of corona product graphs

zbMATH Keywords

boundsmetric dimensionNP-hardnesssimultaneous metric dimensionsimultaneous metric generatorfamilies of trees

Mathematics Subject Classification ID

Trees (05C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)

Cites Work

• Reducibility among Combinatorial Problems
• Resolvability in graphs and the metric dimension of a graph
• On the metric dimension of some families of graphs
• On the Metric Dimension of Cartesian Products of Graphs
• On classes of regular graphs with constant metric dimension
• Metric dimension of some distance-regular graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the metric dimension of Grassmann graphs
• Landmarks in graphs
• Factor domination in graphs
• Metric bases in digital geometry
• Structure-activity maps for visualizing the graph variables arising in drug design
• On Metric Generators of Graphs
• The metric dimension of the lexicographic product of graphs
• The metric dimension of the lexicographic product of graphs
• On the metric dimension of corona product graphs
• Locating and total dominating sets in trees
• The metric dimension and metric independence of a graph
• Conditional resolvability in graphs: a survey
• The metric dimension of Cayley digraphs of abelian groups.

Cited In (14)

• Edge metric dimension of some graph operations
• Metric Dimension and Zero Forcing Number of Two Families of Line Graphs
• The Local metric dimension of the lexicographic product of graphs
• The adjacency dimension of graphs
• Title not available (Why is that?)
• Simultaneous resolvability in families of corona product graphs
• The simultaneous strong metric dimension of graph families
• The simultaneous fractional dimension of graph families
• Mixed metric dimension of graphs
• On adjacency metric dimension of some families of graph
• The simultaneous metric dimension of families composed by lexicographic product graphs
• Title not available (Why is that?)
• The simultaneous local metric dimension of graph families
• On the \(k\)-partition dimension of graphs

This page was built for publication: The simultaneous metric dimension of graph families

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