The threshold dimension of a graph

DOI10.1016/J.DAM.2020.08.007zbMATH Open1450.05020arXiv2001.09168OpenAlexW3081036497MaRDI QIDQ2004085FDOQ2004085

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

Publication date: 14 October 2020

Published in: Discrete Applied Mathematics (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 a graph $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 emph{irreducible}; otherwise, we say that $G$ is reducible. If $H$ is a graph having $G$ as a spanning subgraph and such that $$, then $H$ is called a threshold graph of $G$. The threshold dimension of a graph is expressed in terms of a minimum number of strong products of paths that admits a certain type of embedding of the graph. A sharp upper bound for the threshold dimension of trees is established. It is also shown that the irreducible trees are precisely those of metric dimension at most 2. Moreover, if $T$ is a tree with metric dimension 3 or 4, then $T$ has threshold dimension $2$. It is shown, in these two cases, that a threshold graph for $T$ can be obtained by adding exactly one or two edges to $T$, respectively. However, these results do not extend to trees with metric dimension $5$, i.e., there are trees of metric dimension $5$ with threshold dimension exceeding $2$.

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

zbMATH Keywords

treesmetric dimensionthreshold dimensionirreducible graphsstrong products of paths

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Resolvability in graphs and the metric dimension of a graph
• On the Metric Dimension of Cartesian Products of Graphs
• Extremal graph theory for metric dimension and diameter
• Metric Dimension of Bounded Width Graphs
• The strong isometric dimension of finite reflexive graphs

Cited In (9)

• Threshold hypergraphs
• The threshold dimension and irreducible graphs
• Some invariants related to threshold and chain graphs
• On the robustness of the metric dimension of grid graphs to adding a single edge
• The simple graph threshold number \(\sigma(r,s,a,t)\) when \(r\geq 3\) is odd and \(a\geq 2\) is even
• Distinguishing threshold of graphs
• The threshold strong dimension of a graph
• On the adjacency matrix of a threshold graph
• The threshold dimension and threshold strong dimension of a graph: a survey

This page was built for publication: The threshold dimension of a graph

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