The threshold strong dimension of a graph

DOI10.1016/J.DISC.2021.112402MaRDI QIDQ2032722zbMATH OpenOpenAlexFDO

Authors Nadia Benakli, Novi H. Bong, Shonda Dueck, Linda Eroh, Beth Novick, Ortrud R. Oellermann

Publication date 14 June 2021

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

bounds for the threshold strong dimensionembeddings in strong products of graphsgraphs with vertex covering number 2 realizable by strong resolving graphsstrong dimension of graphsthreshold strong dimensionthreshold strong dimension and trees

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Distance in graphs (05C12) Paths and cycles (05C38)

Abstract: Let $G$ be a connected graph and $u,v$ and $w$ vertices of $G$. Then $w$ is said to {em strongly resolve} $u$ and $v$, if there is either a shortest $u$-$w$ path that contains $v$ or a shortest $v$-$w$ path that contains $u$. A set $W$ of vertices of $G$ is a {em strong resolving set} if every pair of vertices of $G$ is strongly resolved by some vertex of $W$. A smallest strong resolving set of a graph is called a {em strong basis} and its cardinality, denoted $$, the {em strong dimension} of $G$. The {em threshold strong dimension} of a graph $G$, denoted $a{u}_s(G)$, is the smallest strong dimension among all graphs having $G$ as spanning subgraph. A graph whose strong dimension equals its threshold strong dimension is called $$-{em irreducible}. In this paper we establish a geometric characterization for the threshold strong dimension of a graph $G$ that is expressed in terms of the smallest number of paths (each of sufficiently large order) whose strong product admits a certain type of embedding of $G$. We demonstrate that the threshold strong dimension of a graph is not equal to the previously studied threshold dimension of a graph. Graphs with strong dimension $1$ and $2$ are necessarily $$-irreducible. It is well-known that the only graphs with strong dimension $1$ are the paths. We completely describe graphs with strong dimension $2$ in terms of the strong resolving graphs introduced by Oellermann and Peters-Fransen. We obtain sharp upper bounds for the threshold strong dimension of general graphs and determine exact values for this invariant for certain subclasses of trees.

Recommendations

• The threshold dimension and threshold strong dimension of a graph: a survey
• The threshold dimension of a graph
• On the strong metric dimension of product graphs
• The threshold dimension and irreducible graphs
• The strong metric dimension of graphs and digraphs

Cites work

• scientific article; zbMATH DE number 3494441 (Why is no real title available?)
• A short note on: there is no graph \(G\) with \(G_{\mathrm{SR}} \cong\)\(K_{r, s},\ r, s \geq 2\)
• Graphs with metric dimension two - a characterization
• Handbook of product graphs
• On Metric Generators of Graphs
• Resolvability in graphs and the metric dimension of a graph
• Strong resolving graphs: the realization and the characterization problems
• The strong metric dimension of graphs and digraphs
• The threshold dimension of a graph

Cited in

(4)

• Note on strong product graph dimension
• The strong isometric dimension of finite reflexive graphs
• The threshold dimension and threshold strong dimension of a graph: a survey
• The threshold dimension of a graph

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

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