The connected metric dimension at a vertex of a graph

DOI10.1016/J.TCS.2018.11.002zbMATH Open1442.05048arXiv1804.08147OpenAlexW2963043627WikidataQ128994851 ScholiaQ128994851MaRDI QIDQ2285124FDOQ2285124

Authors: Linda Eroh, Cong X. Kang, Eunjeong Yi 

Publication date: 16 January 2020

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Resolvability in graphs and the metric dimension of a graph
• Über eine Eigenschaft der ebenen Komplexe
• On the Metric Dimension of Cartesian Products of Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• On \(k\)-dimensional graphs and their bases
• Landmarks in graphs
• Families of regular graphs with constant metric dimension
• Title not available (Why is that?)
• Title not available (Why is that?)
• The metric dimensions of a complete \(n\)-partite graph and its Cartesian product with a path
• A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs
• The effect of vertex or edge deletion on the metric dimension of graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• The dissimilarity characteristic of Husimi trees

Cited In (9)

• Title not available (Why is that?)
• On the connected metric dimension of graphs and their complements
• The threshold dimension and irreducible graphs
• A note on metric dimension
• Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
• Maker-breaker resolving game
• Learning to compute 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)