Extremal results for graphs of bounded metric dimension

DOI10.1016/J.DAM.2021.11.015MaRDI QIDQ2065772zbMATH OpenOpenAlexFDO

Authors Suchir Kaustav, Antoine Labelle, Jesse Geneson

Publication date 13 January 2022

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

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

zbMATH Keywords

edge metric dimensionextremal functionsmetric dimensionpattern avoidance

Mathematics Subject Classification ID

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

Abstract: Metric dimension is a graph parameter motivated by problems in robot navigation, drug design, and image processing. In this paper, we answer several open extremal problems on metric dimension and pattern avoidance in graphs from (Geneson, Metric dimension and pattern avoidance, Discrete Appl. Math. 284, 2020, 1-7). Specifically, we construct a new family of graphs that allows us to determine the maximum possible degree of a graph of metric dimension at most $k$, the maximum possible degeneracy of a graph of metric dimension at most $k$, the maximum possible chromatic number of a graph of metric dimension at most $k$, and the maximum $n$ for which there exists a graph of metric dimension at most $k$ that contains $K_{n,n}$. We also investigate a variant of metric dimension called edge metric dimension and solve another problem from the same paper for $n$ sufficiently large by showing that the edge metric dimension of $P_n^d$ is $d$ for $ngeq{d}^{d-1}$. In addition, we use a probabilistic argument to make progress on another open problem from the same paper by showing that the maximum possible clique number of a graph of edge metric dimension at most $k$ is $2^{Theta(k)}$. We also make progress on a problem from (N. Zubrilina, On the edge dimension of a graph, Discrete Math. 341, 2018, 2083-2088) by finding a family of new triples $(x,y,n)$ for which there exists a graph of metric dimension $x$, edge metric dimension $y$, and order $n$. In particular, we show that for each integer $k>0$, there exist graphs $G$ with metric dimension $k$, edge metric dimension $3^k(1-o(1))$, and order $3^k(1+o(1))$.

Recommendations

• Metric dimension and pattern avoidance in graphs
• Graphs with the edge metric dimension smaller than the metric dimension
• Extremal Graph Theory for Metric Dimension and Diameter
• On the edge metric dimension of graphs
• Extremal graph theory for metric dimension and diameter

Cites work

• Edge metric dimension of some generalized Petersen graphs
• Edge metric dimension of some graph operations
• Edge version of metric dimension and doubly resolving sets of the necklace graph
• Extremal graph theory for metric dimension and diameter
• Graphs with the edge metric dimension smaller than the metric dimension
• scientific article; zbMATH DE number 3494441 (Why is no real title available?)
• scientific article; zbMATH DE number 3544092 (Why is no real title available?)
• Landmarks in graphs
• Metric bases in digital geometry
• Metric dimension and pattern avoidance in graphs
• On graphs with the maximum edge metric dimension
• On Metric Generators of Graphs
• On the edge dimension of a graph
• On the edge metric dimension of convex polytopes and its related graphs
• On the Metric Dimension of Cartesian Products of Graphs
• Resolvability and the upper dimension of graphs
• Resolvability in graphs and the metric dimension of a graph
• Structure-activity maps for visualizing the graph variables arising in drug design
• Uniquely identifying the edges of a graph: the edge metric dimension

Cited in

(14)

• On optimal realizations of finite metric spaces by graphs
• On the robustness of the metric dimension of grid graphs to adding a single edge
• Truncated metric dimension for finite graphs
• Extremal graph theory for metric dimension and diameter
• Extremal metrics on graphs. I
• On extremal graphs with bounded girth
• Extremal Graph Theory for Metric Dimension and Diameter
• Bounding the order of a graph using its diameter and metric dimension: a study through tree decompositions and VC dimension
• Resolvability and convexity properties in the Sierpiński product of graphs
• Resolving vertices of graphs with differences
• Complexity and equivalency of multiset dimension and ID-colorings
• Fault tolerance for metric dimension and its variants
• Fault tolerance of metric basis can be expensive
• Throttling for metric dimension and its variants

This page was built for publication: Extremal results for graphs of bounded metric dimension

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