Truncated Metric Dimension for Finite Graphs

DOI10.1016/J.DAM.2022.04.021MaRDI QIDQ6371365arXivFDO

Authors Rafael Frongillo, Jesse Geneson, Manuel E. Lladser, Richard C. Tillquist, Eunjeong Yi

Publication date 27 June 2021

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.DAM.2022.04.021

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)

arXiv classification

math.CO

Abstract: A graph $G=(V,E)$ with geodesic distance $d(cdot,cdot)$ is said to be resolved by a non-empty subset $R$ of its vertices when, for all vertices $u$ and $v$, if $d(u,r)=d(v,r)$ for each $rinR$, then $u=v$. The metric dimension of $G$ is the cardinality of its smallest resolving set. In this manuscript, we present and investigate the notions of resolvability and metric dimension when the geodesic distance is truncated with a certain threshold $k$; namely, we measure distances in $G$ using the metric $d_k(u,v):=mind(u,v),k+1$. We denote the metric dimension of $G$ with respect to $d_k$ as $$. We study the behavior of this quantity with respect to $k$ as well as the diameter of $G$. We also characterize the truncated metric dimension of paths and cycles as well as graphs with extreme metric dimension, including graphs of order $n$ such that $$ and $$. We conclude with a study of various problems related to the truncated metric dimension of trees.

This page was built for publication: Truncated Metric Dimension for Finite Graphs

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