On the security of the STR key exchange protocol

1.   Introduction and preliminary results

Metric dimension is an important parameter in metric graph theory that has appeared in numerous applications of graph theory, as diverse as, facility location problems, pharmaceutical chemistry ^[5,6], long range aids to navigation, navigation of robots in networks ^[17], combinatorial optimization ^[21] and sonar and coast guard Loran ^[23], to name a few. Metric dimension is a generalization of affine dimension to arbitrary metric spaces (provided a resolving set exists).

In a connected graph $G$, the distance $d(u, v)$ between two vertices $u, v\in V(G)$ is the length of a shortest path between them. Let $W = \{w_{1}, w_{2}, \dots,$ $w_{k}\}$ be an ordered set of vertices of $G$ and let $v$ be a vertex of $G$. The representation $r(v|W)$ of $v$ with respect to $W$ is the $k$-tuple $(d(v, w_{1}), d(v, w_{2}),$ $d(v, w_{3}), \ldots, d(v, w_{k}))$. $W$ is called a resolving set ^[6] or locating set ^[23] if every vertex of $G$ is uniquely identified by its distances from the vertices of $W$, or equivalently, if distinct vertices of $G$ have distinct representations with respect to $W$. A resolving set of minimum cardinality is called a basis for $G$ and this cardinality is the metric dimension of $G$, denoted by $\beta(G)$ ^[3].

For a given ordered set of vertices $W = \{w_{1}, w_{2}, \ldots, w_{k}\}$ of a graph $G$, the ith component of $r(v|W)$ is 0 if and only if $v = w_{i}$. Thus, to show that $W$ is a resolving set it is sufficient to verify that $r(x|W)\neq r(y|W)$ for each pair of distinct vertices $x, y \in V(G)\backslash W$.

A useful property in computing the metric dimension denoted by $\beta(G)$ is the following lemma:

Lemma 1.1. ^[25] Let $W$ be a resolving set for a connected graph $G$ and $u, v \in V(G)$. If $d(u, w) = d(v, w)$ for all vertices $w\in V(G)\setminus\{u, v\}$, then $\{u, v\}\cap W\neq\emptyset$.

Motivated by the problem of uniquely determining the location of an intruder in a network, the concept of metric dimension was first introduced by Slater in ^[23,24] and studied independently by Harary and Melter in ^[9]. Applications of this invariant to the navigation of robots in networks are discussed in ^[17] and applications to chemistry in ^[6] while applications to problem of pattern recognition and image processing, some of which involve the use of hierarchical data structures are given in ^[18].

Let $\mathcal{F}$ be a family of connected graphs $G_{n}: \mathcal{F} = (G_{n})_{n\geq 1}$ depending on $n$ as follows: the order $|V(G)| = \varphi(n)$ and $\lim\limits_{n\rightarrow\infty}\varphi(n) = \infty$. If there exists a constant $C > 0$ such that $\beta(G_n)\leq C$ for every $n\geq 1$ then we shall say that $\mathcal{F}$ has bounded metric dimension; otherwise $\mathcal{F}$ has an unbounded metric dimension.

If all graphs in $\mathcal{F}$ have the same metric dimension (which does not depend on $n$), $\mathcal{F}$ is called a family with constant metric dimension ^[15]. A connected graph $G$ has $\beta(G) = 1$ if and only if $G$ is a path ^[6]; cycles $C_{n}$ have metric dimension $2$ for every $n\geq 3$. Also generalized Petersen graphs $P(n, 2)$, antiprisms $A_{n}$ and circulant graphs $C_{n}(1, 2)$ are families of graphs with constant metric dimension ^[15]. Recently some classes of regular graphs with constant metric dimension have been studied in ^[13,20]. An example of a family which has bounded metric dimension is the family of prisms. Also generalized Petersen graphs $P(n, 3)$ have bounded metric dimension ^[10].

Note that the problem of determining whether $\beta(G) < k$ is an $NP$-complete problem ^[8]. Some bounds for this invariant, in terms of the diameter of the graph, are given in ^[17] and it was shown in ^[6,17,18,19] that the metric dimension of trees can be determined efficiently. It appears unlikely that significant progress can be made in determining the dimension of a graph unless it belongs to a class for which the distances between vertices can be described in some systematic manner.

The metric dimension of families of graph having unbounded metric dimension is an interesting problem in the theory of resolving set. In ^[3], it was shown that the wheel graph $W_n$ have unbounded metric dimension with $\beta(W_{n}) = \lfloor\frac{2n+2}{5}\rfloor$ for every $n\geq 7$. Later, Javaid et al. ^[26] show that the graph $J_{2n}$ deduced from the wheel $W_{2n}$ by alternately deleting $n$ spokes has unbounded metric dimension with $\beta(J_{2n}) = \lfloor\frac{2n}{3}\rfloor$ for every $n\geq 4$.

Recently, the metric dimension of some wheel related graphs and the convex polytopes generated by wheel related graph are studied by Imran et al. ^[14] and Siddiqui et al. ^[22], respectively, where they have provided an exact formula for the metric dimension of several class of wheel related graphs and shown that all those families have unbounded metric dimension. Further result about the unbounded metric dimension of graphs was derived by Abbas et al. in ^[1] and U. Ali et al. in ^[27]. In this context, it is natural to ask for characterization of graphs with unbounded metric dimension. In this paper, we have extended this study and determined a family of graph that is deduced from wheel graph by removing $k$ consecutive spokes and shown that this family of graph has unbounded metric dimension. It is also worth mentioning that this family of graph have many interesting graph-theoretic properties and have been studied intensively in the literature; for example the chromaticity of this family was investigated in ^[7]. In this paper, the exact value of metric dimension of $W(n, k)$ is computed. Further, the exchange property for resolving set of $W(n, k)$ has also been studied, it is shown that exchange property does not hold for the resolving sets of graph $W(n, k)$.

In what follows all indices $i$ which do not satisfy inequalities $1\leq i\leq n$ will be taken modulo $n$.

2.   On metric basis of wheel graph with $k$-consecutive missing spokes

A wheel graph denoted by $W_{n}$ is defined as $W_{n}\cong C_{n}+K_{1}$, Where $C_{n}: v_{1}, v_{2}, v_{3}, \dots, v_{n}$ for $n\geq 3$ is cycle of length $n$. Suppose $v_{1}, v_{2}, v_{3}, ..., v_{n}$ are the vertices of the outer cycle $C_{n}$ of $W_{n}$ and $v$ be the central vertex of $W_{n}$. If $p, q$ be the positive integers such that $1\leq p < q \leq n$, then $v_{p+1}, v_{p+2}, v_{p+3}, ......, v_{q-1}$ are the vertices in the gap determined by the vertices $v_{p}$ and $v_{q}$, and the size of the gap is denoted by $G_{q-p-1}$ is $q-p-1$. Any two gaps $G_{q-p-1}$ and $G_{s-r-1}$ determined by the vertices $v_{p}, v_{q}$ and $v_{r}, v_{s}$ respectively are said to be the neighboring gaps if $v_{q} = v_{r}$.

Definition: A wheel graph with $k$-consecutive missing spokes denoted by $W(n, k)$ can be obtained by deleting $k$-consecutive spokes from the wheel graph denoted by $W_{n}$. The graph $W(n, k)$ is depicted in the Figure 1. In the following theorem, the metric dimension of the graph $W(n, k)$ is determined. The proof of this theorem is given at the end of this section.

Theorem 2.1. Let $W(n, k)$ denote the wheel graph with $k$-consecutive missing spokes with $k\geq 1$, then $\beta(W(n, k)) = \lceil\frac{2n-2k-2}{5}\rceil$ for $n\geq 5$.

To prove this theorem, we need to prove some lemmas.

In the following result, the upper bound for the metric dimension of $W(n, k)$ is derived.

Lemma 2.1. For every positive integers $n\geq 5$ and $k\geq 1$, we have

Proof. Let

be a set of vertices of the graph $W(n, k)$. In order to show that $B$ is a resolving set for the graph $W(n, k)$; we consider an arbitrary vertex $y\in V(W(n, k)\setminus B)$.

Then there are following possibilities for the choice of $y$:

$\bullet$ The vertex $y$ belong to a gap of size $\lceil\frac{k}{2}\rceil+3$ of $B$. From the construction of set $B$, it is evident that $\{v_{1}, v_{2}, v_{3}, v_{4}, v_{n-k+i}: \lceil\frac{k+1}{2}\rceil+1\leq i\leq k\}$ are the vertices in the gap of size $\lceil\frac{k}{2}\rceil+3$ determined by the vertices $v_{n-k+\lceil\frac{k+1}{2}\rceil}$ and $v_{5}$. The representation of these vertices are given below:

Which shows that every vertex in the gap of size $\lceil\frac{k}{2}\rceil+3$ has a unique representation (see Figure 2).

$\bullet$ $y$ belong to a gap of size $\lceil\frac{k}{2}\rceil$ of $B$. From the construction of set $B$, it is evident that $\{v_{1}, v_{2}, v_{3}, v_{4}, v_{n-k+i}: \lceil\frac{k+1}{2}\rceil+1\leq i\leq k\}$ are the vertices in the gap of size $\lceil\frac{k}{2}\rceil$ determined by the vertices $v_{n-k+\lceil\frac{k+1}{2}\rceil}$ and $v_{5}$. The representation of these vertices are given below:

Which shows that every vertex in the gap of size $\lceil\frac{k}{2}\rceil+3$ has a unique representation (see Figure 2).

$\bullet$ $y$ belong to a gap of size 2 of B. Let $v_{p+1}$ and $v_{p+2}$ be the vertices in the gap of size 2 determined by the vertices $v_{p}$ and $v_{p+3}$. If $y = v_{p+1}$, then it is the unique vertex that has distance 1 and 3 from $v_{p}$ and $v_{n}$, respectively, and distance 2 from all other vertices of $B$. If $y = v_{p+2}$, then it is again the unique vertex that has distance 1 and 3 from $v_{3}$ and $v_{3}$, respectively, and has distance 2 from all other vertices of $B$.

$\bullet$ $y$ belong to a gap of size 1 of B. In this case, let $v_{p+1}$ be the vertex in the gap of size one determined by the vertices $v_{p}$ and $v_{p+2}$; then the vertex $v_{p+1}$ is the unique vertex that has distance 1 from $v_{p}$ and $v_{p+2}$.

The above discussion implies that, every vertex of the graph $W(n, k)$ has unique representation with respect to the set $B$. Hence $B$ is a resolving set that show that

If we delete the vertices $v_{n-k-1}, v_{n-k-2}, \dots, v_{n-1}, v_{n}$ from the graph denoted by $W(n, k)$, then the vertex set of the new graph denoted by $G_{1}$ is

From the construction, $G_{1}$ is isomorphic to the join of the path graph $P_{n-k}$ and $K_{1}$. That is $G_{1}\cong P_{n-k}+K_{1}$, as shown in Figure 3.

Lemma 2.2. Every basis of the graph $G_1$ satisfy the following conditions:

(i) A gap determine by any vertex from $v_{1}$ to $v_{n-k}$ is at most of size 3.

(ii) There is at most one gap in the basis set of size $3$.

(iii) At least one of $v_{n-k}, v_{n-k-1}$ and $v_{n-k-2}$ must belong to basis set.

(iv) The central vertex $v_{\circ}$ does not belong to any of the basis.

(v) If a gap in any of basis contains at least two vertices; then its neighboring gap contain at most one vertex

Proof. Let $B_{1}$ be the arbitrary basis of graph denoted by $G_{1}$. We prove that $B_1$ satisfy conditions $(i)-(v)$.

(i): If there exist a gap of size 4 having the vertices $\{v_{p}, v_{p+1}, v_{p+2}, v_{p+3}\}$. But in this case, we have $r(v_{p+1}|B_{1}) = r(v_{p+2}|B_{2}) = (2, 2, 2, ..., 2, 2)$, a contradiction. Thus, any gap determine by any vertex from $v_{1}$ to $v_{n-k}$ is at most of size 3.

(ii): Suppose on contrary, that there exist two gaps of size $3$. Let $\{v_{p}, v_{p+1}, v_{p+2}\}$ and $\{v_{q}, v_{q+1}, v_{q+2}\}$ are the vertices in these two gaps. Then, we have $r(v_{p+1}|B) = r(v_{q+1}|B) = (2, 2, 2, ..., 2, 2)$, a contradiction. Hence, there is at most one gap in $B_{1}$ of size $3$

(iii): At least one of $v_{n-k}, v_{n-k-1}$ and $v_{n-k-2}$ must belong to $B_{1}$, otherwise $v_{n-k}$ and $v_{n-k-1}$ have same representation. Similarly one of the $v_{1}, v_{2}$ and $v_{3}$ also belong to $B_{1}$.

(iv): Since $v_{\circ}$ is at the distance 1 to all the vertices of $G$ and can be removed from any resolving set. Therefore $B_1$ being a minimal resolving set can not contain $v_{\circ}$. This implies that he central vertex $v_{\circ}$ does not belong to $B_1$.

(v): Let there are two consecutive gaps of size at least 2 and $\{v_{p+1}, v_{p+2}\}$ and $\{v_{p+4}, v_{p+5}\}$ be the vertices in these gaps determined by $v_{p}$, $v_{p+3}$ and $v_{p+3}$, $v_{p+6}$, respectively. Then the vertices $v_{p+2}$ and $v_{p+4}$ have same representations, a contradiction. Hence, if a gap of $B_{1}$ contains at least two vertices; then its neighboring gap contain at most one vertex.

Lemma 2.3. Every subset of the vertex set of the graph $G_1$ satisfying the conditions of Lemma 2.2 is a resolving set.

Proof. Let $B_1$ is a subset of $V(G_1$ satisfying all the conditions of Lemma 2.2. Let $y\in V(G_{1}\backslash B_{1})$ be an arbitrary element, we show that $y$ has unique representation. There are following possibilities for the choice of $y$.

$\bullet$ $y$ belong to a gap of size 3 of $B_{1}$. Assume that the vertices $v_{p}, v_{p+1}, v_{p+2}, v_{p+3}, v_{p+4}$ belong to the rim vertices; where $v_{p}$ and $v_{p+4} \in B_{1}$. The vertex $v_{p+1}$ then has distance one from $v_{p}$ and 2 from all other vertices of $B_{1}$, and $v_{p+2}$ then has distance 2 from all vertices of $B_{1}$. Similarly the vertex $v_{p+3}$ is it distance 1 from $v_{p+4}$ and has distance 2 from all other vertices of $B_{1}$. By condition $(i)$ and $(ii)$ of Lemma 2.2; these vertices have unique representation.

$\bullet$ $y$ belong to a gap of size 2 of $B_{1}$. Let the vertices $v_{p}, v_{p+1}, v_{p+2}, v_{p+3}$ belong to the rim vertices such that $v_{p}$ and $v_{p+3}\in B_{1}$. We have two cases here:

If $y_{1} = v_{p+1}$, then it has distance 1 from $v_{p}$ and distance 2 from all other vertices of $B_{1}$. By condition $(v)$ of Lemma 2.2; these vertices have unique representation.

If $y_{1} = v_{p+2}$, then it is at distance 1 from $v_{p+3}$ and distance 2 from all vertices of $B_{1}$. Again, by condition $(v)$ of Lemma 2.2; these vertices have unique representation and no other vertex have this representation.

$\bullet$ $y$ belong to a gap of size 1 of $B_{1}$. Assume that $\{v_{p}, y_{1}, v_{p+1}\}$ belong to the rim vertices; where $v_{p}$ and $v_{p+1} \in B_{1}$. Then $y$ is the only vertex having distance 1 from both the vertices $v_{p}$ and $v_{p+1}$, so the representation of $y$ is unique.

Thus, we conclude that any set $B_{1}$ satisfying all conditions of Lemma 2.2 is the resolving set of the graph $G_{1}\cong P_{n-k}+K_{1}$.

In the following result, the metric dimension of the graph $G_{1}\cong P_{n-k}+K_{1}$ is computed.

Lemma 2.4. For every positive integer $m\geq 3$, $\beta(G_{1}) = \lceil\frac{2m-2}{5}\rceil$, where $m = n-k$.

Proof. Define the set $B_{1}$ as follows,

The set $B_{1}$ satisfy all the conditions of Lemma 2.2. Therefore $B_{1}$ is the resolving set for $G_{1}$. Which shows that

To prove the lower bound, let $B_{1}$ be the basis for the graph $G_{1}$. To show that $|B_{1}|\geq \lceil\frac{2m-2}{5}\rceil$, we have the following two cases:

Case 1: When $|B_{1}| = 2l$, where $l\geq 1$.

$\bullet$ If $B_{1}$ has a gap of size 3, then from Lemma 2.2, $B_{1}$ can contain at most one gap of size 3, $l-1$ gaps of size 2, $l$ gaps of size 1. So we have

$\bullet$ If $B_{1}$ has no gap of size 3, then again from Lemma 2.2, $B_{1}$ contain no gap of size 3, at most $l$ gaps of size 2 and $l$ gaps of size 1. Hence we have

Case 2: When $|B_{1}| = 2l+1$, where $l\geq 1$.

$\bullet$ If $B_{1}$ has a gap of size 3; then from Lemma 2.2, $B_{1}$ can contain at most one gap of size 3, $l-1$ gaps of size 2 and $l$ gaps of size 1. Therefore, we have

$\bullet$ If $B_{1}$ has no gap of size 3, then again from Lemma 2.2, $B_{1}$ contain no gap of size 3, at most $l$ gaps of size 2 and $l$ gaps of size 1. We have

The above discussion implies that

From Eqs (2.1) and (2.2), we get

We now are in position to prove the main theorem of our paper.

Proof of Theorem 2.1: The upper bound for the metric dimension of the wheel graph with $k$-consecutive missing spokes denoted by $W(n, k)$ is given by Lemma 2.1:

where $n\geq 5$ and $k\geq 1$. On the other hand from the Lemma 2.4, we have

where $G_{1}\cong W(n, k)\setminus\{v_{n-k+i}: 1\leq i\leq k\}$. Now by putting the value of $m = n-k$, we get

Since $G_{1}$ is the subetaaph of graph $W(n, k)$, therefore

Hence, from Equations (3) and (4), it follows that

where $n\geq 5$ and $k\geq 1$. This completes the proof.

3.   Exchange property for resolving set in $W(n, k)$

We have seen that a subset $W$ of vertices of a graph $G$ is a resolving set if every vertex in $G$ is uniquely determined by its distances to the vertices of $W$. Resolving sets behave like bases in a vector space in that each vertex in the graph can be uniquely identified relative to the vertices of these sets. But though resolving sets do share some of the properties of bases in a vector space, they do not always have the exchange property from linear algebra. Resolving sets are said to have the exchange property in $G$ if whenever $S$ and $R$ are minimal resolving sets for $G$ and $r\in R$, then there exists $s\in S$ so that $(S\setminus\{s\})\cup \{r\}$ is a minimal resolving set ^[2].

If the exchange property holds for a graph $G$, then every minimal resolving set for $G$ has the same size and algorithmic methods for finding the metric dimension of $G$ are more feasible. Thus to show that the exchange property does not hold in a given graph, it is sufficient to show two minimal resolving sets of different size. However, since the converse is not true, knowing that the exchange property does not hold does not guarantee that there are minimal resolving sets of different size.

The following results concerning exchange property for resolving sets were deduced in ^[2].

Theorem 3.1. ^[2] The exchange property holds for resolving sets in trees.

Theorem 3.2. ^[2] For $n\geq 8$, resolving sets do not have the exchange property in wheels $W_{n}$.

The exchange property for resolving sets of the graph $W(n, k)$ has been discussed in the next theorem.

Theorem 3.3. The exchange property does not hold for the resolving sets of the graph $W(n, k)$ for every positive integers $n-k\geq 10$ and $k\geq 1$.

Proof. To show that exchange property does not hold on the resolving sets of graph $W(n, k)$, we need to show that there are two minimal resolving sets of different size.

Since the set $B = \{v_{\lceil\frac{5i}{2}\rceil}: 2\leq i\leq\lceil\frac{2n-2k-2}{5}\rceil-1\}\cup\{v_{n-k-1}, v_{n-\lfloor\frac{k-1}{2}\rfloor}\}$ is the metric basis of the graph $W(n, k)$, so indeed it is a minimal resolving set for $W(n, k)$ having cardinality $m = n-k$.

Now define another subset of the vertex set of the graph $W(n, k)$, for $k+10$ and $k\geq 1$ as follows:

$B^{*}$ satisfy all the condition of Lemma 2.2, so is a resolving set of $W(n, k)$ having cardinality $\lceil\frac{n-2k-2}{4}\rceil+\lceil\frac{n-2k}{4}\rceil+1$. Next, we show that $B^{*}$ is also minimal resolving set by proving that there does not exist any $b\in B^{*}$ such that $B^{*} \setminus\{b\}$ is still a resolving set. There are the following three cases for the choice of $b$:

Case 1: If $b = v_{n-\lfloor\frac{k-1}{2}\rfloor}$; then removal of $v_{n-\lfloor\frac{k}{2}\rfloor}$ would yield a gap of size $k+2$. By claim (1), this is not possible.

Case 2: If $b\in \{v_{4i+1}:1\leq i\leq\lceil\frac{n-2k-2}{4}\rceil\}$ then removal of $b$ can be considered as follows: If $b = v_{5}$ for $i = 1$, then it would cause two vertices having same representation as $r(v_{5}|B^{*}) = r(v_{7}|B^{*}) = (1, 2, 2, 2, ..., \lfloor\frac{k}{2}\rfloor+3)$. When $b = v_{9}$ for $i = 1$, then it would cause two vertices having same representation, i.e. $r(v_{9}|B^{*}) = r(v_{11}|B^{*}) = (2, 2, 1, 2, ..., \lfloor\frac{k}{2}\rfloor+3)$. Similarly, we can show that if we remove any basis vertex $v_{4i+1}$ for $1\leq i \leq \lceil\frac{n-2k-2}{4}\rceil$, then $v_{4i+1}$ and $v_{4i+3}$ will have the same representations.

Case 3: If $b\in \{v_{4j+2}:1\leq j\leq\lceil\frac{n-2k}{4}\rceil-1\}$. In this case by removing $b = v_{6}$ for $j = 1$, would cause two vertices having same representations which are $r(v_{5}|B^{*}) = r(v_{7}|B^{*}) = (1, 2, 2, 2, ..., \lfloor\frac{k-1}{2}\rfloor+3)$. If $b = v_{9}$ for $i = 1$, then it would cause two vertices having same representations, i.e. $r(v_{9}|B^{*}) = r(v_{11}|B^{*}) = (2, 2, 1, 2..., \lfloor\frac{k-1}{2}+3\rfloor)$. Similarly, it can be shown that for any choice of the vertex $b$ from the set of vertices $\{v_{4j+2}: 1\leq j \leq \lceil\frac{2n-2k}{5}\rceil-1 \}$; the vertices $v_{4j+1}$ and $v_{4j+3}$ will have the same representations.

This shows that $B^{*}$ is a minimal resolving set, which completes the proof.

4.   Conclusions

The problem of determining whether $\beta(G) < k$ is an $NP$-complete problem. It is natural to ask for characterization of graphs with bounded or unbounded metric dimension. In general, it appears unlikely that significant progress can be made in this regard unless it belongs to a class for which the distances between vertices can be described in some systematic manner. There have been significant work done in literature to explore the families of graphs with unbounded metric dimension (See ^{[1,3,14,22,26,27]}). In this context, we have explore a family that is constructed from wheel graph by removing $k$ consecutive spokes and it is shown that this family of graph has unbounded metric dimension. This results also add further support to a negative answer of an open problem raised in ^[12]. It is further shown that exchange property for resolving set does not hold for this family of graphs.

Acknowledgments

The authors are thankful to the referees for their valuable suggestions.

Conflict of interest

The authors declare no conflict of interest.