|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
The Threshold Strong Dimension of a Graph | | Nadia Benakli
; Novi H Bong
; Shonda M. Dueck
; Linda Eroh
; Beth Novick
; Ortrud R. Oellermann
; | | Date: |
10 Aug 2020 | | 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 $eta_s(G)$, the {em strong dimension} of $G$. The {em threshold
strong dimension} of a graph $G$, denoted $ au_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 $eta_s$-{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 $eta_s$-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. | | Source: | arXiv, 2008.04282 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER