Source author record

Matthew J. H. Murphy

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

2works

2topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

The Threshold Dimension and Irreducible Graphs

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 $β(G)$ , 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 $G$ , denoted $τ(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 $β(G) = τ(G)$ , then $G$ is said to be irreducible. We 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, we show that every planar graph of order $n$ has threshold dimension $O (\log_2 n)$ . We show that several infinite families of graphs, known to have metric dimension $3$ , are in fact irreducible. Finally, we show that for any integers $n$ and $b$ with $1 \leq b < n$ , there is an irreducible graph of order $n$ and metric dimension $b$ .

preprint2020arXiv

The Threshold Dimension of a Graph

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 $β(G)$ , 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 $τ(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 $β(G) = τ(G)$ , 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 $β(H)=τ(G)$ , 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$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.