The connected metric dimension at a vertex of a graph

DOI10.1016/J.TCS.2018.11.002MaRDI QIDQ2285124zbMATH OpenOpenAlexWikidataFDO

Authors Linda Eroh, Cong X. Kang, Eunjeong Yi

Publication date 16 January 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

distancemetric dimensionconnected metric dimensionconnected resolving set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12)

Abstract: The notion of metric dimension, $dim(G)$, of a graph $G$, as well as a number of variants, is now well studied. In this paper, we begin a local analysis of this notion by introducing $cdi{m}_G(v)$, emph{the connected metric dimension of $G$ at a vertex $v$}, which is defined as follows: a set of vertices $S$ of $G$ is a emph{resolving set} if, for any pair of distinct vertices $x$ and $y$ of $G$, there is a vertex $zinS$ such that the distance between $z$ and $x$ is distinct from the distance between $z$ and $y$ in $G$. We call a resolving set $S$ emph{connected} if $S$ induces a connected subgraph of $G$. Then, $cdi{m}_G(v)$ is defined to be the minimum of the cardinalities of all connected resolving sets which contain the vertex $v$. The emph{connected metric dimension of $G$}, denoted by $cdim(G)$, is $mincdi{m}_G(v):vinV(G)$. Noting that $1ledim(G)lecdim(G)lecdi{m}_G(v)le|V(G)|-1$ for any vertex $v$ of $G$, we show the existence of a pair $(G,v)$ such that $cdi{m}_G(v)$ takes all positive integer values from $dim(G)$ to $|V(G)|-1$, as $v$ varies in a fixed graph $G$. We characterize graphs $G$ and their vertices $v$ satisfying $cdi{m}_G(v)in1,|V(G)|-1$. We show that $cdim(G)=2$ implies $G$ is planar, whereas it is well known that there is a non-planar graph $H$ with $dim(H)=2$. We also characterize trees and unicyclic graphs $G$ satisfying $cdim(G)=dim(G)$. We show that $cdim(G)-dim(G)$ can be arbitrarily large. We determine $cdim(G)$ and $cdi{m}_G(v)$ for some classes of graphs. We further examine the effect of vertex or edge deletion on the connected metric dimension. We conclude with some open problems.

Recommendations

• Resolvability in graphs and the metric dimension of a graph
• Extremal graph theory for metric dimension and diameter
• On the connected metric dimension of graphs and their complements
• The effect of vertex or edge deletion on the metric dimension of graphs
• The metric dimension of Cartesian products of graphs

Cites work

• scientific article; zbMATH DE number 5776159 (Why is no real title available?)
• scientific article; zbMATH DE number 3494441 (Why is no real title available?)
• scientific article; zbMATH DE number 3544092 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1749658 (Why is no real title available?)
• scientific article; zbMATH DE number 1895692 (Why is no real title available?)
• scientific article; zbMATH DE number 227006 (Why is no real title available?)
• A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs
• Families of regular graphs with constant metric dimension
• Landmarks in graphs
• On \(k\)-dimensional graphs and their bases
• On the Metric Dimension of Cartesian Products of Graphs
• Resolvability in graphs and the metric dimension of a graph
• The dissimilarity characteristic of Husimi trees
• The effect of vertex or edge deletion on the metric dimension of graphs
• The metric dimensions of a complete \(n\)-partite graph and its Cartesian product with a path
• Über eine Eigenschaft der ebenen Komplexe

Cited in

(11)

• scientific article; zbMATH DE number 7560302 (Why is no real title available?)
• On the connected metric dimension of graphs and their complements
• The threshold dimension and irreducible graphs
• Bounds on the connected local dimension of graphs in terms of the marked dimension and the clique number
• A note on metric dimension
• Maker-breaker resolving game
• Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
• Learning to compute the metric dimension of graphs
• The effect of vertex or edge deletion on the metric dimension of graphs
• Truncated metric dimension for finite graphs
• On distance-\(s\) locating and distance-\(t\) dominating sets in graphs

This page was built for publication: The connected metric dimension at a vertex of a graph

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