Behrooz Bagheri Ghavam Abadi and Ali Zaghian: On the Forcing Dimension of a Graph, p.129-136

Abstract:

A set $W\subseteq V(G)$ is called a resolving set, if for each two distinct vertices $u,v\in V(G)$ there exists $w\in W$ such that $d(u,w)\neq d(v,w)$, where $d(x,y)$ is the distance between the vertices $x$ and $y$. A resolving set for $G$ with minimum cardinality is called a metric basis. The forcing dimension $f(G, dim)$ (or $f(G)$) of $G$ is the smallest cardinality of a subset $S\subset V(G)$ such that there is a unique basis containing $S$. The forcing dimensions of some well-known graphs are determined. In this paper, among some other results, it is shown that for large enough integer $n$ and all integers $a, b$ with $0\le a \le b \le n$ and $b \ge 1$, there exists a nontrivial connected graph $G$ of order $n$ with $f(G) = a$ and $dim(G) = b$ if $\{a, b\} \ne \{0, 1\}$.

Key Words: Resolving set, metric basis, forcing dimension, basis number.

2000 Mathematics Subject Classification: Primary: 05C12;
Secondary: 05C15, 05C62.

Download the paper in pdf format here.