The threshold dimension and irreducible graphs

DOI10.7151/DMGT.2359zbMATH Open1504.05081arXiv2002.11048OpenAlexW3088577461MaRDI QIDQ2107754FDOQ2107754

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)

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

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

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

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)

Cites Work

• Graph Classes: A Survey
• Resolvability in graphs and the metric dimension of a graph
• On the metric dimension of some families of graphs
• On the Metric Dimension of Cartesian Products of Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Landmarks in graphs
• Families of regular graphs with constant metric dimension
• Graphs with metric dimension two - a characterization
• Extremal graph theory for metric dimension and diameter
• Metric dimension of bounded width graphs
• The threshold dimension of a graph

Cited In (4)

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

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)