The threshold dimension and irreducible graphs

DOI10.7151/DMGT.2359MaRDI QIDQ2107754zbMATH OpenOpenAlexFDO

Authors Matthew J. H. Murphy, L. A. S. Mól, Ortrud R. Oellermann

Publication date 2 December 2022

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

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

zbMATH Keywords

distance in graphsmetric dimensionthreshold dimension

Mathematics Subject Classification ID

Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: Let $G$ be a graph, and let $u$, $v$, and $w$ be vertices of $G$. If the distance between $u$ and $w$ does not equal the distance between $v$ and $w$, then $w$ is said to resolve $u$ and $v$. The metric dimension of $G$, denoted $$, is the cardinality of a smallest set $W$ of vertices such that every pair of vertices of $G$ is resolved by some vertex of $W$. The threshold dimension of $G$, denoted $au(G)$, is the minimum metric dimension among all graphs $H$ having $G$ as a spanning subgraph. In other words, the threshold dimension of $G$ is the minimum metric dimension among all graphs obtained from $G$ by adding edges. If $$, then $G$ is said to be irreducible. We give two upper bounds for the threshold dimension of a graph, the first in terms of the diameter, and the second in terms of the chromatic number. As a consequence, we show that every planar graph of order $n$ has threshold dimension $O(lo{g}_{2}n)$. We show that several infinite families of graphs, known to have metric dimension $3$, are in fact irreducible. Finally, we show that for any integers $n$ and $b$ with $1leqb<n$, there is an irreducible graph of order $n$ and metric dimension $b$.

Review text

The threshold dimension of a graph \(G\) is defined as the minimum metric dimension among all graphs \(H\) having \(G\) as a spanning subgraph. If the threshold dimension of \(G\) equals the metric dimension of \(G\), then \(G\) is said to be irreducible. These notions were introduced in a recent article by the current authors [Discrete Appl. Math. 287, 118--133 (2020; Zbl 1450.05020)]. In this paper, the authors give two upper bounds for the threshold dimension of a graph, the first in terms of the diameter, and the second in terms of the chromatic number. As a consequence, the latter bound implies that the threshold dimension of every planar graph of order \(n\) is less than \(4 \log_{2} n\). It is shown that several infinite families of graphs, known to have metric dimension 3, are in fact irreducible. For example, if \(n \geq 5\), then the generalized Petersen graph \( P(n, 2)\) is irreducible. Finally, the authors proves that for any integers \(n\geq 2\) and \(b\) with \(1 \leq b \leq n-1\), there is a connected irreducible graph of order \(n\) and metric dimension \(b\). Two open questions conclude the paper.

Recommendations

• The threshold dimension of a graph
• On metric dimension of graphs and their complements
• Estimates of the metric dimension of a graph in terms of its diameter and the number of vertices
• The effect of vertex or edge deletion on the metric dimension of graphs
• Graphs with the edge metric dimension smaller than the metric dimension
• On the metric dimension of a graph
• The connected metric dimension at a vertex of a graph
• A note on \(k\)-metric dimensional graphs
• On path related graphs with constant metric dimension
• Resolvability in graphs and the metric dimension of a graph

Cites work

• Extremal graph theory for metric dimension and diameter
• Families of regular graphs with constant metric dimension
• Graph Classes: A Survey
• Graphs with metric dimension two - a characterization
• 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 dimension of bounded width graphs
• On the Metric Dimension of Cartesian Products of Graphs
• On the metric dimension of some families of graphs
• Resolvability in graphs and the metric dimension of a graph
• The threshold dimension of a graph

Cited in

(4)

• The threshold dimension of a graph
• The threshold strong dimension of a graph
• Threshold Dimension of Graphs
• Metric dimension and its variations of chain graphs

This page was built for publication: The threshold dimension and irreducible graphs

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