The threshold dimension and irreducible graphs

DOI10.7151/DMGT.2359MaRDI QIDQ2107754zbMATHOpenAlexFDO

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)

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

zbMATH Keywords

metric dimensiondistance in graphsthreshold dimension

Mathematics Subject Classification ID

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

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$.

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

• scientific article; zbMATH DE number 3494441 (Why is no real title available?)
• scientific article; zbMATH DE number 3544092 (Why is no real title available?)
• 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
• 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 strong dimension of a graph
• The threshold dimension of a graph
• Metric dimension and its variations of chain graphs
• Threshold Dimension of 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)