The simultaneous metric dimension of graph families

DOI10.1016/J.DAM.2015.06.012zbMATH Open1327.05186OpenAlexW118899274WikidataQ57974183 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)

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

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)

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.

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

Cites Work

• scientific article; zbMATH DE number 3494441 (Why is no real title available?)
• scientific article; zbMATH DE number 3544092 (Why is no real title available?)
• Conditional resolvability in graphs: a survey
• Factor domination in graphs
• Landmarks in graphs
• Locating and total dominating sets in trees
• Metric bases in digital geometry
• Metric dimension of some distance-regular graphs
• On Metric Generators of Graphs
• On classes of regular graphs with constant metric dimension
• On the Metric Dimension of Cartesian Products of Graphs
• On the metric dimension of Grassmann graphs
• On the metric dimension of corona product graphs
• On the metric dimension of some families of graphs
• Reducibility among combinatorial problems
• Resolvability in graphs and the metric dimension of a graph
• Structure-activity maps for visualizing the graph variables arising in drug design
• The metric dimension and metric independence of a graph
• The metric dimension of Cayley digraphs of abelian groups.
• The metric dimension of the lexicographic product of graphs
• The metric dimension of the lexicographic product of graphs

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 no real title available?)
• Simultaneous resolvability in graph families
• 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
• 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)