Metric dimension and pattern avoidance in graphs

DOI10.1016/J.DAM.2020.03.001MaRDI QIDQ777351zbMATH OpenOpenAlexFDO

Authors Jesse Geneson

Publication date 7 July 2020

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

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

zbMATH Keywords

edge metric dimensionextremal problemsmetric dimensionpattern avoidance

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35)

Abstract: In this paper, we prove a number of results about pattern avoidance in graphs with bounded metric dimension or edge metric dimension. We show that the maximum possible number of edges in a graph of diameter $D$ and edge metric dimension $k$ is at most $(lfloorfrac2D3floor+1{)}^k+ksu{m}_{i=1}^{lceilfracD3ceil}(2i{)}^{k-1}$, sharpening the bound of $$ from Zubrilina (2018). We also show that the maximum value of $n$ for which some graph of metric dimension $leqk$ contains the complete graph $K_n$ as a subgraph is $n=2^k$. We prove that the maximum value of $n$ for which some graph of metric dimension $leqk$ contains the complete bipartite graph $K_{n,n}$ as a subgraph is $2^{Theta(k)}$. Furthermore, we show that the maximum value of $n$ for which some graph of edge metric dimension $leqk$ contains $K_{1,n}$ as a subgraph is $n=2^k$. We also show that the maximum value of $n$ for which some graph of metric dimension $leqk$ contains $K_{1,n}$ as a subgraph is $3^k-O(k)$. In addition, we prove that the $d$-dimensional grids $pro{d}_{i=1}^d{P}_{r_i}$ have edge metric dimension at most $d$. This generalizes two results of Kelenc et al. (2016), that non-path grids have edge metric dimension $2$ and that $d$-dimensional hypercubes have edge metric dimension at most $d$. We also provide a characterization of $n$-vertex graphs with edge metric dimension $n-2$, answering a question of Zubrilina. As a result of this characterization, we prove that any connected $n$-vertex graph $G$ such that $edim(G)=n-2$ has diameter at most $5$. More generally, we prove that any connected $n$-vertex graph with edge metric dimension $n-k$ has diameter at most $3k-1$.

Recommendations

• The metric dimension and girth of graphs
• On the metric dimension of a graph
• The Metric Dimension of Circulant Graphs
• On the metric dimension of circulant graphs
• On metric dimension of graphs and their complements
• Metric dimension of some distance-regular graphs
• On the metric dimension of incidence graphs
• Metric dimension of Andrásfai graphs
• scientific article; zbMATH DE number 6739348

Cites work

• Extremal graph theory for metric dimension and diameter
• scientific article; zbMATH DE number 3544092 (Why is no real title available?)
• Landmarks in graphs
• Metric bases in digital geometry
• On the edge dimension of a graph
• Resolvability in graphs and the metric dimension of a graph
• Uniquely identifying the edges of a graph: the edge metric dimension

Cited in

(24)

• Edge metric dimension of some graph operations
• Edge metric dimensions via hierarchical product and integer linear programming
• Extremal results for graphs of bounded metric dimension
• Vertex and edge metric dimensions of unicyclic graphs
• Metric dimensions vs. cyclomatic number of graphs with minimum degree at least two
• On the robustness of the metric dimension of grid graphs to adding a single edge
• On vertices contained in all or in no metric basis
• A note on the metric and edge metric dimensions of 2-connected graphs
• Learning to compute the metric dimension of graphs
• Vertex and edge metric dimensions of cacti
• Truncated metric dimension for finite graphs
• The effect of vertex and edge deletion on the edge metric dimension of graphs
• Graphs with the edge metric dimension smaller than the metric dimension
• Bounding the order of a graph using its diameter and metric dimension: a study through tree decompositions and VC dimension
• scientific article; zbMATH DE number 7560302 (Why is no real title available?)
• On metric dimensions of hypercubes
• On the edge dimension and the fractional edge dimension of graphs
• Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
• Fault-tolerant resolvability of some graphs of convex polytopes
• Fractional local edge dimensions of a graph
• Fault tolerance for metric dimension and its variants
• The edge metric dimensions of convex polytopes
• Theoretical analysis and approximate calculation of metric dimension problem of graphs
• Throttling for metric dimension and its variants

This page was built for publication: Metric dimension and pattern avoidance in graphs

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