The threshold dimension and irreducible graphs (Q2107754)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The threshold dimension and irreducible graphs |
scientific article |
Statements
The threshold dimension and irreducible graphs (English)
0 references
2 December 2022
0 references
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.
0 references
threshold dimension
0 references
metric dimension
0 references
distance in graphs
0 references