The threshold dimension of a graph

DOI10.1016/J.DAM.2020.08.007MaRDI QIDQ2004085zbMATH OpenOpenAlexFDO

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

Publication date 14 October 2020

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

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

zbMATH Keywords

irreducible graphsmetric dimensionstrong products of pathsthreshold dimensiontrees

Mathematics Subject Classification ID

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

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

Review text

In this paper, the threshold dimension of a graph \(G\), denoted by \(\tau (G)\) is defined as the minimum metric dimension among all graphs \(H\) having \(G\) as a spanning subgraph, or the minimum metric dimension among all graphs obtained from \(G\) by adding edges. If \(\beta (G)= \tau (G)\), where \(\beta (G)\) denotes the metric dimension of \(G\), then \(G\) is said to be irreducible; otherwise, \(G\) is called reducible. If \(H\) is a graph having \(G\) as a spanning subgraph and such that \(\beta (H)=\tau (G)\), then \(H\) is called a threshold graph of \(G\). The first part of this paper gives an expression for the threshold dimension of a graph in terms of a minimum number of strong products of paths (each of sufficiently large order) that admits a certain type of embedding of the graph. Using this result, it is proved that there are trees of arbitrarily large metric dimension having threshold dimension equal to two. The second part of the paper focuses on the threshold dimension of trees, establishing a sharp upper bound for the threshold dimension of trees and showing that 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 and in each of these two cases a threshold graph for \(T\) can be obtained by adding exactly one or two edges to \(T\), respectively but there are trees of metric dimension 5 with threshold dimension exceeding 2. Two open problems conclude the paper.

Recommendations

• The threshold dimension and irreducible graphs
• The metric dimension and metric independence of a graph
• The threshold strong dimension of a graph
• The threshold dimension and threshold strong dimension of a graph: a survey
• 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
• Graphs with metric dimension two - a characterization
• Handbook of product graphs
• scientific article; zbMATH DE number 3494441 (Why is no real title available?)
• scientific article; zbMATH DE number 3544092 (Why is no real title available?)
• Metric dimension of bounded width graphs
• On the Metric Dimension of Cartesian Products of Graphs
• Resolvability in graphs and the metric dimension of a graph
• The strong isometric dimension of finite reflexive graphs

Cited in

(12)

• Threshold hypergraphs
• The threshold strong dimension of a graph
• The threshold dimension and threshold strong dimension of a graph: a survey
• The threshold dimension and irreducible graphs
• On the robustness of the metric dimension of grid graphs to adding a single edge
• On the adjacency matrix of a threshold graph
• The simple graph threshold number (r,s,a,t) when r 3 is odd and a 2 is even
• Threshold Dimension of Graphs
• Metric dimension and its variations of chain graphs
• Sharp bound on the truncated metric dimension of trees
• Distinguishing threshold of graphs
• Some invariants related to threshold and chain graphs

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)