Graphs with mixed metric dimension three and related algorithms

1.   Introduction

One of the important features of graph metric generator is that its different version can be introduced according to the required scenario or application. Up till now, a lot of research work has been carried out on metric generators and its various versions starting from Slater ^[14], Haray ^[7] and then contributed by a number of authors ^{[2,3,4,5,6,7,8,9,10,11,12]}. The notion of graph metric generator was primarily studied due to its basic property of identification of intruder in the network as all the nodes in the network can be uniquely localized by a certain set of vertices called metric generator. However, in the situation, when an intruder can approach the system not only through nodes but also by manipulating the connections between the nodes (i.e., edges), then a basic metric generator may not be able to locate the intruder. This leads to the motivation of constructing a metric generator having capabilities of distinguishing both vertices and edges so that this type of situation can be handled. Kelenc et al. ^[9] proposed a metric generator variant referred as mixed metric generator which can identified both vertices and edges of graph simultaneously. They analyzed different properties of mixed metric generator. In particular, they characterized the graphs of order $n$ having mixed dimension $2$ and $n$. They proved that graph has mixed dimension two if and only if it is a path graph and has mixed dimension $n$ if and only if it is a complete graph. They also determined mixed dimension of some well- known families of graph like path graph, cycle graph, cartesian product with path graphs, etc. The mixed metric dimension of petersen graph was determined by Raza and Ji ^[13]. The mixed metric dimension for unicyclic graphs was investigated in ^[15]. In ^[1], the necessary and sufficient conditions for graphs of order at least 3 having mixed fault-tolerant generators are established. Moreover, a mixed fault-tolerant metric generator is determined for graphs having shortest cycle length at least 4. Danas et al. ^[6] presented three general lower bounds for mixed metric dimension of graphs. They also compare the new bounds with already existing bounds in literature.

As the minimum mixed dimension for a simple connected graph $J\ncong P_{n}$ with $n\geq 3$ is three and one of such graph is cycle graph ^[9], so it is natural to seek all graphs having mixed dimension three. The focus of this paper is to characterize such graphs and to develop an algorithm to determine "whether a simple connected graph $J$ with $n\geq 3$ vertices such that $J\ncong P_{n}$ has mixed dimension three or not?" We also classify all unicyclic graphs with mixed dimension three. To characterize the graphs having mixed dimension three and to develop algorithm for this, we use the idea of neihbourhood of vertices and vertex distance partitions which was used in ^[16] for characterization of graphs having metric dimension two. To recall, for a graph $Q,$ the distance between two vertices is the length of the shortest path between them, whereas, the distance between a vertex $x$ and an edge $e = yz$ is given as $d(x, e) = \min\{d(x, y), d(x, z)\}$. The subset $M = \{m_1, m_2, \cdots, m_{k}\}\subseteq V(Q)$ is referred as mixed metric generator or mixed generator, if distance vectors of any two members $x, y\in V(Q)\cup E(Q)$ are distinct, i.e., $r(x|M)\neq r(y|M)$, where distance vector $r(x|M) = (d(x, m_{1}), d(x, m_{2}, \cdots, d(x, m_{k}))$. The smallest mixed generator is called mixed basis and the number of elements in mixed basis is called mixed dimension. It is represented as $\dim _{m}(Q)$. For $x\in V(Q)$, the collection $\{X_{0}, X_{1}, \cdot, X_{k}\}$ is referred as distance partition of $V(Q)$ relative to the vertex $x$ if $X_{0} = \{x\}$and $X_{j} = \{y \in V(Q): d(x, y) = j$, for $1\leq j\leq k$, where $k$ is the eccentricity of $x$ in $Q$. The sets $X_{0}, X_{1}, \cdot, X_{k}$ are referred as distance partite sets. The open neighbourhood $N(v)$ of $v\in V(G)$ is defined as $N(v) = \{x\in V(G): x\sim v\}$. The eccentricity $e(v)$ of any vertex $v\in V(G)$ is the maximum distance of $v$ in $V(G)$, i.e., $e(v) = \max_{x\in V(G)} d(x, v)$. the vertex of degree one is referred as pendant vertex and vertex adjacent to pendant vertex is called support vertex. A unicyclic graph is a simple graph with exactly one cycle.

2.   Mixed basis for trees and unicyclic graphs

Definition 2.1. Consider a graph $G$ of order $r\geq 1$ with $V(G) = \{v_1, v_2, \cdots, v_r\}$ and $r$ paths $P_{s_i}$ of length $s_{i}$ with $s_i\geq 1$. Then the graph obtained from $G$ by identifying a pendant vertex of a path $P_{s_{i}}$ with $v_i\in V(G)$ such that $i = 1, \ldots, r$. Then this new graph is denoted by $\Gamma_{G}(P_{s_{1}}, P_{s_{2}}, \cdots, P_{s_{r}})$.

Example 2.1. Consider a wheel graph of order 8, where $V(W_8) = \{v_1, v_2, v_3, v_4, v_5, v_6, v_7, v_8\}$. Then $G$ is the new graph obtained by identifying the pendent vertices of paths of lengths $P_{2}, P_{2}, P_{3}, P_{3}$ with vertices $v_2, v_3, v_5, v_7$ and path of length one with all remaining vertices $\Gamma_{W_8}(P_{1}, P_{2}, P_{2}, P_{1}, P_{3}, P_{1}, P_{3}, P_{1})$ as shown in Figure 1.

Example 2.2. The unicycle graph $U_n = \Gamma_{C_8}(P_{3}, P_{1}, P_{2}, P_{1}, P_{1}, P_{3}, P_{1}, P_{1})$ is obtained by $C_8$ and identifying the pendant vertices of paths $P_3, P_2$ and $P_3$ with vertices $u_{1}, u_{3},$ and $u_{6}$, respectively. This is shown in Figure 2.

Remark. If $P_{m}:v_{1}-v_{2}-\cdots-v_{m}$ is a path with end vertices $v_{1}$ and $v_{m}$. Then the graph $\Gamma_{p_{m}}(P_{1}, \cdots, P_{1}, P_{r})$ is a path on $m+r-1$ vertices for $r\geq 1$, whereas for $r\geq 2$ the graph $\Gamma_{p_{m}}(P_{1}, P_{r}, P_{1} \cdots, P_{1})$ is a tree which is not a path. The tree $\Gamma_{p_{m}}(P_{1}, P_{2}, P_{1} \cdots, P_{1})$ is shown in the Figure 3.

Remark. It can be easily seen that $\Gamma_{G}(P_{s_{1}}, P_{s_{2}}, \cdots, P_{s_{r}}) = G \cup_{i = 1}^{r}P_{s_{i}}$ such that $G\cap P_{s_{i}} = v_{i}$ for all $i = 1, \cdots, r$ and $P_{s_{i}}\cap P_{s_{j}} = \phi$ for all $i\neq j$. Moreover $\Gamma_{G}(P_{s_{1}}, P_{s_{2}}, \cdots, P_{s_{r}})$ is subgraph of rooted product of $G\circ_{a} P_{t}$, where $t = \max_{i = 1}^{r}s_{i}$ and $a$ is a pendant vertex of $P_{t}.$

Theorem 2.1. ^[9] If a graph $G$ contains pendant vertices, then any mixed metric generator of $G$ must contain all pendant vertices of $G$.

Theorem 2.2. Let $T_{n}\ncong P_{n}$ be a tree with $n\geq 3$ vertices. Then $dim_m(T_n) = 3$ if and only if $T_{n}\cong \Gamma_{P_{t}}(P_{1}, \cdots, P_{1}, P_{r}, P_{1}, \cdots, P_{1})$, where $P_{r}$ is attached to a vertex which is not pendant vertex such that $r\geq2$ and $n = t+r-1$ and $t\geq 3$.

Proof. Suppose $dim_{m}(T_{n}) = 3$. Since $T_{n}\ncong P_{n}$, $T_{n}$ contains at least three pendant vertices. As from Theorem 2.1, any mixed metric contains all the pendant vertices, $T_{n}$ has mixed dimension three only if it contains exactly three pendant vertices, say $v_{1}$, $v_{2}$ and $v_{3}$. If $v_{1}$, $v_{2}$ and $v_{3}$ are attached to exactly one support vertex, say $s$, then we claim that $T_{n}\cong K_{1, 3}$ for otherwise there is a vertex $s_{1}$ different from $v_{1}$, $v_{2}$ and $v_{3}$ but adjacent to $s$. If $s_{1}$ is a pendant vertex, then we have four pendant vertex, a contradiction. Thus there must be a vertex adjacent to $s_{1}$, say $s_{2}$. Now $s_{2}\neq v_{1}, v_{2}, v_{3}$ or $s$ for otherwise we have a cycle which contradict the fact that $T_{n}$ is a tree. Continuing in this way, we have distinct vertices $s_{1}, s_{2}, \cdots$. But as we have finite number of vertices, this process must end and there ia an index $k$ such that either $s_{k} = s_{j}$ for some $1\leq j < k$ or $s_{k} = v_{1}, v_{2}, v_{3},$ or $s$. In either case, we have a cycle, a contradiction. Hence if there is exactly one support vertex, then $T_{n}\cong K_{1, 3}$. Now we suppose that $s$ and $s'$ are two support vertices attached to vertices $v_{1}$ and $v_{2}$, respectively. Let $d(s, s') = h$, then as $v_{1}$ and $v_{2}$ are pendant vertices, so $d(v_{1}, v_{2}) = h+2$. Let $t = h+2$. Then we have a path $P_{t}$ of length $t$ from $v_{1}$ to $v_{2}$. Since $T_{n}$ is connected and $v_{3}$ does not lie on the path $P_{t}$ so the vertex $v_{3}$ is linked to every vertex of path $P_{t}$ through some path. Now let $v_i$ be the vertex on $P_{t}$ which is nearer to $v_{3}$. Clearly $v_i\neq v_{1}, v_{2}$. Let $d(v_{i}, v_{3}) = r$ i.e., we have a path $P_{r}$ whose end vertex $v_i$ coincides with $i-th$ vertex of path $P_{t}$. Then the subgraph induced by $V(P_{t})$ and $V(P_{r_{i}})$ is isomorphic to $\Gamma_{P_{t}}(P_{1}, \cdots, P_{r_{i}}, \cdots P_{1})$. Clearly $v_i$ is not a pendant vertex of $P_{t}$. Now we claim that all the vertices of $T_{n}$ either lie on path $P_{t}$ or on $P_{r}$. For if $(V(P_{t})\cup V(P_{r_{i}}))\cap V(T_{n})\neq \phi$, then there exists a vertex $w_{1}$ adjacent to some vertex of $V(P_{t})\cup V(P_{r_{i}})$. Without loss of generality, assume that $w_{1}$ is adjacent to some vertex of $P_{t}$. If degree of $w_{1}$ is one, than $T_{n}$ has four pendant vertices, a contradiction. Therefore $deg(w_{1})\geq 2$. Since $T_{n}$ does not contain any cycle, $w_{1}$ is not adjacent to any vertex of $V(P_{t})$ and $V(P_{r_{i}})$. Thus we have a vertex $w_{2}\in T_{n}\setminus (V(P_{t})\cup V(P_{r}))$. By continuing this process, we get vertices $w_{1}, w_{2}, \cdots \in T_{n}\setminus (V(P_{t})\cup V(P_{r}))$. Since $T_{n}$ is finite, there exists some index $k$ such that $w_{j} = w_{k}$ for $1\leq j < k$. But then $T_{n}$ contains a cycle, a contradiction. Hence $G\cong\Gamma_{P_{t}}(P_{1}, \cdots, P_{1}, P_{r}, P_{1}, \cdots, P_{1})$ such that $P_{r}$ is not attached to pendant vertex of $P_{t}$ and $n = t+r-1$. □

Corollary 1. A tree $T_{n}$ has mixed dimension 3 if and only if degree sequence of $T_{n}$ is $(1, 1, 1\underbrace{2, \cdots, 2}_{(n-4)times}, 3).$

Corollary 2. Given the degree sequence of tree $T_{n}$, it is decidable in time $O(1)$ whether $T_{n}$ has mixed metric dimension three.

Proof. From Corollary 1, it can be seen that if we have degree sequence of a tree, we only need to check the first four elements and last two elements of degree sequence. Since a tree has always at least two pendant vertices, first two entries will always contain one's for otherwise it is not a degree sequence of a tree. Thus to determine whether a tree has mixed dimension three, we only have to check the third, fourth and last two elements of degree sequence. This completes the proof. □

Lemma 2.3. Let $U$ be a unicyclic graph with $dim_m(U) = 3$. Then any cycle vertex has degree at most 3 and any non-cycle vertex has degree at most 2.

Proof. Consider a unicyclic graph $U$, with a unique cycle of length $n$. Suppose that there exists a cycle vertex $c_{1}$ such that $deg(c_1) > 3$. Now label the cycle vertices as $\{c_1, c_2, \cdots, c_n\}$. Let $v_1$ and $v_2$ be two non-cycle vertices attached to cycle vertex $c_1$. Then there exists two distinct pendant vertices $l_1$ and $l_2$ such that $c_1-v_1-\cdots -l_1$ and $c_1-v_2-\cdots-l_2$ are the shortest paths having lengths $r$ and $s$, respectively. Then $l_1, l_2$ must belong to $M$. Since $dim_m(U) = 3$, there exists $l_1, l_2\neq m\in M$ such that $M = \{l_1, l_2, m\}$ is a mixed metric basis. First assume that $m$ is any vertex of the maximal subtree containing $c_{1}$. Then consider $x = c_1$ and $y = c_1c_2$, where $c_2\in N(c_1)$ be a cycle vertex. Since the vertex $c_1$ is more closer to $l_{1}, l_{2}$ and $m$ than $c_{2}$, the coordinate vectors of $x$ and $y$ with reference to $M$ are $r(x|M) = (r, s, t) = r(y|M)$, a contradiction. Hence we may assume that $m$ does not belong to the maximal subtree containing $c_{1}.$ Now suppose $n$ is odd, then $c = c_\frac{n-1}{2}$ and $c' = c_\frac{n+1}{2}$(antipodal vertices) are equidistant from $c_{1}$. Without loss of generality, assume $c = c_\frac{n-1}{2}$ is more closer to $m$ than $c'$. Then for a pair of elements $x = c$ and $y = c'c$, $d(m, c) = d(m, cc')$. Since $c, c'$ are antipodal vertices, $d(cc', c_{1}) = d(c, c_{1}) = d(c', c_{1})$. This further implies that $d(l_1, x) = d(l_1, c_1)+d(c_1, c) = d(l_1, c_1)+d(c_{1}, cc') = d(l_1, y)$. Similarly $d(l_2, x) = d(l_2, c_1)+d(c_1, c) = d(l_2, c_1)+d(c_{1}, cc') = d(l_2, y)$, i.e., $r(c|M) = r(y|M)$, a contradiction. Now if $n$ is even then the vertices $c_{\frac{n}{2}}$ and $c_{\frac{n}{2}+2}$ are equidistant from $c_{1}$. Clearly $e_{1} = c_{\frac{n}{2}}c_{\frac{n}{2}+1}, e_{2} = c_{\frac{n}{2}+1}c_{\frac{n}{2}+2}\in E(U)$ and $d(e_{1}, l_{i}) = d(e_{2}, l_{i}) = d(l_{i}, c_{\frac{n}{2}}) = d(l_{i}, c_{\frac{n}{2}+2})$ for $i = 1, 2$. Now if $d(m, c_{\frac{n}{2}+1}) < d(m, c_{\frac{n}{2}}), d(c_{\frac{n}{2}+2}, m)$, then $d(e_{1}, m) = d(m, e_{2})$ which implies that $r(e_{1}|M) = r(e_{2}|M)$, a contradiction. Thus without loss of generality, assume that $m$ is more closer to $c_{\frac{n}{2}}$ than $c_{\frac{n}{2}+1}$ and $c_{\frac{n}{2}+2}$. But then $r(e_{1}|M) = r(c_{\frac{n}{2}}|M)$. All cases lead to a contradiction. Thus degree of cycle vertex is at most 3.

Now let $y$ be any non-cycle vertex with degree greater than 2. Then there exist at least two distinct pendant vertices $l_{1}, l_{2}$ such that there is exactly one path from $y$ to $l_{i}$ for $i = 1, 2$. By Theorem, $l_{1}, l_{2}\in M$. Since $dim_m(U) = 3$, $M = \{l_1, l_2, m\}$ is a mixed metric basis. If $c_{1}$ is a first cycle vertex closer to $y$. Then using the same arguments as above, it can be shown that $M$ is not mixed resolving set. □

Theorem 2.4. Let $U_n$ be a unicycle graph. Then $dim_m(U_n) = 3$ if and only if either $U_n\cong C_n$ or $U_{n}\cong \Gamma_{C_{m}}(P_{r}, \underbrace{P_{1}, \cdots, P_{1}}_{m-1\; times})$, where $m+r-1 = n$ (i.e., tadpole graph) or $U_{n}\cong \Gamma_{C_{m}}(P_{r_{1}}, \underbrace{P_{1} \cdots, P_{1}}_{i\; times}, P_{r_{2}},$ $\underbrace{P_{1}, \cdots P_{1}}_{m-2-i\; times})$, where $i\geq 0$ and $m+r_{1}+r_{2}-2 = n$ or $U_{n}\cong \Gamma_{C_{m}}(P_{r_{1}}, \underbrace{P_{1} \cdots, P_{1}}_{i\; times}, P_{r_{2}}, \underbrace{P_{1}, \cdots P_{1}}_{j\; times}, P_{r_{3}},$ $\underbrace{P_{1}, \cdots P_{1}}_{m-i-j-3\; times})$ such that $m+r_{1}+r_{2}+r_{3}-3 = n$ and $i+j+3\geq s$, where $s = m/2+1$ if $m$ is even and $s = (m+1)/2$ otherwise.

Proof. Suppose $dim_{m}(U_{n}) = 3$. As from Theorem 2.1, any mixed metric contains all the pendant vertices, $U_{n}$ has metric dimension three only if it contains at most three pendant vertices. Now by Lemma 2.3, degree of each cycle vertex is at most 3. If all the cycle vertices have degree two than $U_{n}\cong C_{n}$. Thus we may assume that there exists at least one cycle vertex of degree three. We claim that there are at most three cycle vertices whose degree is 3, for if there are more than three vertices, then there must exists at least four pendant vertices, a contradiction. Hence, there are at most three cycle vertices whose degree is 3.

Let $x$ be the cycle vertex of $deg(x)\geq3$. Suppose $T_x$ be the subtree attached at $x$ containing unique cycle vertex $x$. We claim that $T_x$ is a path, for if $T_x$ is not a path then there must exists at least one vertex $w\in T_{x}$ such that $deg(w)\geq3$. If $w = x$ then $deg(w)$ in $U_n$ is at least 5, which contradicts Lemma 2.3. If $w$ is a non- cycle vertex with $deg(w)\geq 3$, then it again contradicts Lemma2.3. This further shows that $U_n$ is a graph in which a path is attached to all cycle vertices having degree at least 3. If there is only one cycle vertex with degree three, then it is easy to see that $U_{n}$ is a tadpole and $U_{n}\cong \Gamma_{C_{m}}(P_{r}, \underbrace{P_{1}, \cdots, P_{1}}_{m-1\; times})$. If $U_{n}$ contains two cycle vertex of degree three, then clearly, $U_{n}\cong \Gamma_{C_{m}}(P_{r_{1}}, \underbrace{P_{1} \cdots, P_{1}}_{i\; times}, P_{r_{2}},$ $\underbrace{P_{1}, \cdots P_{1}}_{m-2-i\; times})$ such that $m+r+t-2 = n$. Now suppose $U_{n}$ contains exactly three cycle vertex of degree three. Then $M = \{u, v, w\}$ consisting of pendant vertices and $U_{n}\cong \Gamma_{C_{m}}(P_{r_{1}}, \underbrace{P_{1} \cdots, P_{1}}_{i\; times}, P_{r_{2}}, \underbrace{P_{1}, \cdots P_{1}}_{j\; times}, P_{r_{3}},$ $\underbrace{P_{1}, \cdots P_{1}}_{m-i-j-3\; times})$, where $m+r_{1}+r_{2}+r_{3}-3 = n$. Let the vertices of $C_{m}$ are ordered as $v = v_{1}, \cdots v_{m}$ such that $u = v_{i}, w = v_{j}$. Suppose $m$ is even but both $i, j\leq m/2$. Now consider the edge $e = v_{m/2}v_{m/2+1}$ and the vertex $v_{m/2}$. As $d(v_{1}, v_{m/2}) = m/2$ and $d(v_{1}, v_{m/2+1}) = m/2+1$, so $d(v_{1}, e) = d(v_{1}, v_{m/2})$. Also as $i, j\leq m/2$, so $v_{m/2}$ is closer to $v_{i} = u$ and $v_{j} = w$ as compared to $v_{m/2+1}$. Hence $r(v_{m/2}|M) = r(e|M)$, a contradiction. Now suppose $m$ is odd but both $i, j\leq (n+1)/2$. Using same arguments, it can be shown that $r(v_{(m+1)/2}|M) = r(v_{(m+1)/2}V_{(m+3)/2}|M)$. It completes the proof □

3.   Structure of graphs having mixed dimension three

Lemma 3.1. Let $M = \{v_{1}, v_{2}, v_{3}\}$ be a mixed metric basis of a graph $G$. Then $|N(v_{i})\cap N(v_{j})|\leq 3$ for all distinct pair of vertices $v_{i}, v_{j}\in M$. Moreover any two distinct vertices in $N(v_{i})\cap N(v_{j})$ for $i\neq j$ are not adjacent.

Proof. Consider distinct pair of vertices $v_{i}, v_{j}\in M$. Suppose $d(v_{i}, v_{k}) = r$ for $v_{k}\neq v_{i}, v_{j}$. Now for any vertex $w\in N(v_{i})\cap N(v_{j})$, $d(w, v_{i}) = 1 = d(w, v_{j})$ so we have

Now clearly, $d(w, v_{k})\geq r-1$ for otherwise we have a path $v_{i}- w-\cdots -v_{k}$ of length less than $r$ between $v_{i}$ and $v_{k}$, a contradiction. Hence

This further implies that only possibilities are $d(w, v_{k}) = r-1, r, r+1$. Now if there are more than three vertices in $N(v_{i})\cap N(v_{j})$, then as $d(w, v_{i}) = 1 = d(w, v_{j})$, the coordinate vectors of at least two vertices in $N(v_{i})\cap N(v_{j})$ with respect to $M$ are same. This leads to a contradiction. Now for $i\neq j$, let $x, y\in N(v_{i})\cap N(v_{j})$ be two distinct vertices such that $x \sim y$. As $d(x, v_{i}) = d(y, v_{i}) = 1$ and $d(x, v_{j}) = d(y, v_{j}) = 1$. Since $M$ is mixed basis, we have $d(x, v_{k})\neq d(y, v_{k})$. Suppose $t = d(x, v_{k}) < d(y, v_{k})$. Then $r(x|M) = (1, 1, t)$ and as $x$ is more closer to $v_{k}$ than $y$ so $d(xy, v_{k}) = d(x, v_{k}) = t$. But then $d(xy|M) = (1, 1, t) = d(x|M)$, i.e., $x$ and the edge $xy$ are not resolved by $M$, a contradiction.□

Lemma 3.2. Let $M = \{v_{1}, v_{2}, v_{3}\}$ be a mixed metric basis of a graph $G$ and $\{V_{i0}, V_{i1}, \cdots, V_{ie(v_{i})}\}$ be the distance partition of $V(G)$ with respect to $v_{i}\in M$, where $e(v_{i})$ is the eccentricity of $v_{i}$. Then $|V_{1i}\cap V_{2j}\cap V_{3k}|\leq 1$ for all $1\leq i\leq e(v_{1})$, $1\leq j\leq e(v_{2})$ and $1\leq k\leq e(v_{3})$

Proof. Suppose on contrary there exists some integers $r\leq e(v_{1})$, $s\leq e(v_{2})$ and $t\leq e(v_{3})$ such that $|V_{1r}\cap V_{1s}\cap V_{1t}| > 1$. Then there exists $a, b \in V(G)$ such that $a, b \in V_{1r}\cap V_{2s}\cap V_{3t}$. Then clearly

i.e., $r(a|M) = r(b|M)$. This leads to a contradiction. □

Lemma 3.3. Let $M = \{v_{1}, v_{2}, v_{3}\}$ be a mixed metric basis of a graph $G$ and $\{X_{i0}, X_{i1}, \cdots, X_{ie(v_{i})}\}$ be the distance partition of $V(G)$ with respect to $v_{i}\in M$. If for some $i, j \in \{1, 2, 3 \}$, $0\leq r\leq e(v_{i})$ and $0\leq s\leq e(v_{j})$, the vertices $a, b \in V_{ir}\cap V_{js}$, then $a$ and $b$ are not adjacent.

Proof. Suppose the vertices $a$ and $b$ are adjacent, i.e., $e = ab\in E(G)$ and $d(a, v_{k}) = t$ for $v_{k}\neq v_{i}, v_{j}$. Then using the same arguments as used in the proof of Lemma 3.1, it can be seen that $d(b, v_{k}) = t-1, t, t+1$. Now $d(b, v_{k})\neq t$ for otherwise $a, b\in V_{ir}\cap V_{js}\cap V_{kt}$ which contradicts Lemma 3.2. If $d(b, v_{k}) = t-1$, then $b$ is more closer to $v_{k}$ than $a$. In this case, $d(b, v_{k}) = d(e, v_{k})$. Now as $a, b \in V_{ir}\cap V_{js}$, therefore $d(b, v_{i}) = r = d(e, v_{i})$ and $d(b, v_{j}) = s = d(e, v_{j})$, i.e., the vertex $b$ and the edge $e = ab$ are not resolved by $M$. Similarly if $d(b, v_{k}) = t+1$, then it can be shown that the vertex $a$ and the $e = ab$ cannot be distinguished by $M$. This leads to a contradiction. □

Lemma 3.4. Let $M = \{v_{1}, v_{2}, v_{3}\}$ be a mixed metric basis of a graph $G$ and $\{V_{i0}, V_{i1}, \cdots, V_{ie(v_{i})}\}$ be the distance partition of $V(G)$ with respect to $v_{i}\in M$. If for some $0\leq r\leq e(v_{i})$, $0\leq s\leq e(v_{j})$ and $0\leq t\leq e(v_{3})$, the vertex $a \in V_{1r}\cap V_{2s} \cap V_{3t}$ and $b \in (V_{1r}\cup V_{1(r+1)})\cap (V_{2s}\cup V_{2(s+1)}) \cap (V_{3t}\cup V_{3(t+1)})$, then $a$ and $b$ are not adjacent.

Proof. As $a \in V_{1r}\cap V_{2s} \cap V_{3t}$ and $b \in (V_{1r}\cup V_{1(r+1)})\cap (V_{2s}\cup V_{2(s+1)}) \cap (V_{3t}\cup V_{3(t+1)})$, so $d(a, v_{i})\leq d(b, v_{i})$ for $i = 1, 2, 3$. Thus if $a$ is adjacent to $b$, i.e., $e = ab\in E(G)$, then $d(e, v_{i}) = d(a, v_{i})$ for all $i$. This further implies that $r(a|M) = r(e = ab|M)$ which contradicts the fact that $M$ is mixed basis. □

Lemma 3.5. Let $M = \{v_{1}, v_{2}, v_{3}\}$ be a mixed metric basis of a graph $G$ and $\{V_{i0}, V_{i1}, \cdots, V_{ie(v_{i})}\}$ be the distance partition of $V(G)$ with respect to $v_{i}\in M$. If for $a \in V_{1r}\cap V_{2s} \cap V_{3t}$ ($0\leq r\leq e(v_{i})$, $0\leq s\leq e(v_{j})$ and $0\leq t\leq e(v_{3})$), there exist $b, c \in (V_{1r}\cup V_{1(r+1)})\cap (V_{2s}\cup V_{2(s+1)}) \cap (V_{3t}\cup V_{3(t+1)})$ such that at least one of $b$ and $c$ must belong to $v_{1r}$, $v_{2s}$ and $v_{3t}$ then $b$ and $c$ are not adjacent.

Proof. If $a$ is equal to one of $b$ and $c$, say $a = c$ then from Lemma 3.4, $a = c$ is not adjacent to $b$. Thus we may assume that $a\neq b, c$. Suppose on contrary $b\sim c$, i.e., $e = bc\in E(G)$. Now $d(a, v_{1}) = r$, $d(a, v_{2}) = s$ and $d(a, v_{3}) = t$. Since at least one of $b$ and $c$ (end points of edge $e$) must belong to $v_{1r}$, $v_{2s}$ and $v_{3t}$, $d(e, v_{1}) = r$, $d(e, v_{2}) = s$ and $d(e, v_{3}) = t$. This implies that $r(a|M) = (r, s, t) = r(e = ab|M)$, a contradiction to the assumption that $M$ is a mixed basis of $G$. □

Lemma 3.6. Let $M$ be a mixed metric basis of a graph $G$ and $\{V_{i0}, V_{i1}, \cdots, V_{ie(v_{i})}\}$ be the distance partition of $V(G)$ with respect to $v_{i}\in M$. If for $a, c\in V_{i}$, there exists $b, d\in (V_{ir}\cup V_{i(r+1)})\cap (V_{js}\cup V_{j(s+1)})\cap(V_{kt}\cup V_{k(t+1)})$ ($i\neq j\neq k$) such that $a, d \in V_{js}$ and $b, c\in V_{kt}$, where $0\leq s\leq e(v_{j})$, $0\leq t \leq e(v_{k})$ then either $a\nsim b$ or $c\nsim d$.

Proof. Suppose on contrary, for $a, c\in V_{i}$, there exists $b, d\in (V_{ir}\cup V_{i(r+1)})\cap (V_{js}\cup V_{j(s+1)})\cap(V_{kt}\cup V_{k(t+1)})$ ($i\neq j\neq k$) such that $a, d \in V_{js}$, $b, c\in V_{kt}$ but $a\sim b$ and $c\sim d$, i.e., $e_{1} = ab, e_{2} = cd \in E(G)$. Since $a, c\in V_{i}$, $a$ and $c$ are more closer to $v_{i}$, than $b$ and $d$, respectively. This shows that $d(e_{1}, v_{i}) = d(a, v_{i}) = r$ and $d(e_{2}, v_{i}) = d(c, v_{i}) = r$. Now as $a, d \in V_{js}$, so $a$ and $d$ are more closer to $v_{j}$, than $b$ and $c$, respectively. This implies that $d(e_{1}, v_{j}) = d(a, v_{j}) = s$ and $d(e_{2}, v_{j}) = d(d, v_{j}) = s$. Similarly we can see that $d(e_{1}, v_{k}) = d(b, v_{k}) = t$ and $d(e_{2}, v_{k}) = d(c, v_{j}) = t$. Thus if $M = \{v_{i}, v_{2}, v_{3}$ is ordered mixed basis of $G$, then $r(e_{1}|M) = (r, s, t) = r(e_{2}|M)$, a contradiction. □

Lemma 3.7. Let $M = \{v_{1}, v_{2}, v_{3}\}$ be a mixed metric basis of a graph $G$ and $\{V_{i0}, V_{i1}, \cdots, V_{ie(v_{i})}\}$ be the distance partition of $V(G)$ with respect to $v_{i}\in M$. Then induced subgraph of any distance partition $V_{ij}$ of any vertex $v_{i}\in M$ is triangle free.

Lemma 3.8. Let $M = \{v_{1}, v_{2}, v_{3}\}$ be a mixed metric basis of a graph $G$ and $\{V_{i0}, V_{i1}, \cdots, V_{ie(v_{i})}\}$ be the distance partition of $V(G)$ with respect to $v_{i}\in M$. Then the maximum degree of any vertex in induced subgraph of any distance partition $V_{ij}$ is at most 2.

Lemma 3.9. Let $M$ be a mixed metric basis of a graph $G$ with $|M| = 3$. Then the maximum degree of any vertex of $M$ is at most 3.

Proof. Let $v_{i}\in M$ be any vertex and let $M = \{v_{i}, v_{j}, v_{k}\}$ be ordered basis of $G$. Suppose $d(v_{i}, v_{j}) = r$ and $d(v_{i}, v_{k}) = t$. Suppose $a\in N(v_{i})$. Then clearly $d(a, v_{j}) = r, r-1$ or $r+1$ and $d(a, v_{k}) = t, t-1$ or $t+1$. We claim that if $d(a, v_{j}) = r$, then $d(a, v_{k})$ must be $t-1$ for otherwise $r(v_{i}|M) = (0, r, t) = r(av_{i}|M)$, i.e., the vertex $v_{i}$ and edge $av_{i}$ are not resolved by $M$. Similarly if $d(a, v_{j}) = r+1$, then $d(a, v_{k}) = t-1$. Also we claim that the distinct vertices $a, c\in N(v_{i})$ with representation $r(a|M) = (1, r, t-1)$ and $r(c|M) = (1, r+1, t-1)$ do not occur simultaneously for otherwise $a, c \in V_{k(t-1)}\cap V_{i1}$, $b = v_{i} = d\in V_{kt}\cap V_{i0}$ and $a, d\in V_{jr}$. By Lemma 3.3, either $a$ is not adjacent to $b = v_{i}$ or $c$ is not adjacent to $d = v_{i}$, a contradiction as both $a, c\in N(v_{i})$. Now we claim that there are at most two vertices in $N(v_{i})$ with distance $r-1$ from $v_{j}$, for if there are at least three distinct vertices $a, b, c\in N(v_{j})$, then their distance representation must be $(1, r-1, t-1)$, $(1, r-1, t)$ and $(1, r-1, t+1)$, respectively. But then $b, c \in V_{j(r-1)}\cap V_{i1}$, $e = v_{i} = f \in V_{jr}\cap V_{i0}$ and $b, e, f\in V_{kt}$. By Lemma 3.3, either $b$ is not adjacent to $e = v_{i}$ or $c$ is not adjacent to $f = v_{i}$, a contradiction as both $b, c\in N(v_{i})$. Thus $N(v_{i})$ can contain at most three vertices; maximum 2 with distance $r-1$ and one with distance $r$ or $r+1$ (but not both). Thus maximum number of vertices in $N(v_{i})$ is 3. □

Theorem 3.10. Let $G$ be a connected graph which is not a tree having mixed metric dimension $3$ and diameter $D$. Then $G$ contains at most $(D^{3}+12D^{2})/2$ vertices.

Proof. For each vertex except basis vertex, the associated coordinate vector with positive coordinates $(\alpha, \beta, \gamma)$, where $1\leq \alpha, \beta, \gamma\leq D$ can be chosen in one of $D^{3}$ ways. The coordinate vector corresponding to basis elements are $(0, \beta_{1}, \gamma_{1})$, $(\alpha_{2}, 0, \gamma_{2})$ and $(\alpha, \beta, 0)$ for some $1\leq \alpha, \beta, \gamma\leq D$. On the other hand, the coordinate vectors are also assigned to edges and these must be distinct from the coordinate vectors of vertices. All the edges except those which are incident with basis elements have positive integers in each coordinate of coordinate vectors. Therefore, these again must be chosen from possible $D^{3}$ coordinate vectors. From Lemma 3.9, the maximum number of edges incident to three basis vertices are 9. Hence maximum number of coordinate vectors which can be assigned to edges and vertices must not exceed $D^{3}+3D^{2}+9D^{2}$. Then this further implies that

As $G$ is connected but not a tree, so it must contain at least $|V(G)|$ edges. Thus (3.3) becomes

Hence

□

Theorem 3.11. Let $G$ be a graph with $n\geq 3$ vertices such that $G$ is not a tree and $\{V_{i0}, V_{i1}, \cdots, V_{ie(v_{i})}\}$ be the distance partition of $V(G)$ with respect to $v_{i}\in V(G)$, where $e(v_{i})$ is the eccentricity of $v_{i}$. Then mixed metric dimension of $G$ is three if and only if there exists three vertices $v_{1}, v_{2}$ and $v_{3}$ which satisfy the following conditions:

1. $|V_{1i}\cap V_{2j}\cap V_{3k}|\leq 1$ for all $1\leq i\leq e(v_{1})$, $1\leq j\leq e(v_{2})$ and $1\leq k\leq e(v_{3})$.

2. If for $a \in V_{1r}\cap V_{2s} \cap V_{3t}$ ($0\leq r\leq e(v_{i})$, $0\leq s\leq e(v_{j})$ and $0\leq t\leq e(v_{3})$), there exists $b, c \in (V_{1r}\cup V_{1(r+1)})\cap (V_{2s}\cup V_{2(s+1)}) \cap (V_{3t}\cup V_{3(t+1)})$ such that at least one of $b$ and $c$ must belong to $v_{1r}$, $v_{2s}$ and $v_{3t}$ then $b$ and $c$ are not adjacent.

3. If for $a, c\in V_{i}$, there exists $b, d\in (V_{ir}\cup V_{i(r+1)})\cap (V_{js}\cup V_{j(s+1)})\cap(V_{kt}\cup V_{k(t+1)})$ ($i\neq j\neq k$) such that $a, d \in V_{js}$ and $b, c\in V_{kt}$, where $0\leq s\leq e(v_{j})$, $0\leq t \leq e(v_{k})$ then either $a\nsim b$ or $c\nsim d$.

Proof. Let $M = \{v_{1}, v_{2}, v_{3}\}$ be a mixed metric basis of a graph $G$. suppose on contrary condition (1) is not satisfied. Then there exists some integers $r\leq e(v_{1})$, $s\leq e(v_{2})$ and $t\leq e(v_{3})$ such that $|V_{1r}\cap V_{1s}\cap V_{1t}| > 1$. Then there exists $a, b \in V(G)$ such that $a, b \in V_{1r}\cap V_{2s}\cap V_{3t}$. Then clearly

i.e., $r(a|M) = r(b|M)$. This leads to a contradiction. Hence condition (1) holds. Also conditions (2) and $3$ are satisfied from Lemma 3.5 and Lemma 3.6.

Conversely suppose that there exists three vertices $v_{1}, v_{2}$ and $v_{3}$ that satisfy all the conditions. We will show that the set $M = \{v_{1}, v_{2}, v_{3} \}$ is mixed metric generator for $G$. Suppose on contrary there exists distinct elements $x, y \in V(G)\cup E(G)$ such that $x$ and $y$ are not resolved by any member of $M$. Then

If $x, y \in V(G)$, then $x, y\in V_{1r}\cap V_{2s} \cap V_{3t}$, i.e., $|V_{1r}\cap V_{2s} \cap V_{3t}|\geq 2$, which contradicts condition (1). Hence for at least one $v_{i}\in M$, $d(x, v_{i})\neq d(y, v_{i})$. Now suppose $x\in V(G)$ and $y = y_{1}y_{2}\in E(G)$. Then from (3.4), we have $x \in V_{1r}\cap V_{2s}\cap V_{3t}$ and $y_{1}, y_{2}\in (V_{1r}\cup V_{1(r+1)})\cap (V_{2s}\cup V_{2(s+1)})\cap (V_{3t}\cup V_{3(t+1)})$ such that at least one of $y_{1}$ and $y_{2}$ must belong to $V_{1r}$, $V_{2s}$ and $V_{3t}$. But then from condition (2), $y_{1}\nsim y_{2}$, which contradicts the assumption that $y = y_{1}y_{2}$ is an edge. Finally, assume that $x = x_{1}x_{2}$ and $y = y_{1}y_{2}$ are two distinct edges. There arise two cases:

Case 1: The edges $x$ and $y$ are not adjacent, i.e., $x_{1}\neq x_{2}\neq y_{1}\neq y_{2}$. Then from (3.4),

Consider the edge $x = x_{1}x_{2}$, by pigeon hole principle, one of $x_{1}$ and $x_{2}$ is more closer to two of $v_{1}$, $v_{2}$ and $v_{3}$. Without lose of generality, assume that $x_{1}$ is more closer to $v_{1}$ and $v_{2}$ than $x_{2}$, i.e., $d(x, v_{1}) = d(x_{1}, v_{1}) = r$ and $d(x, v_{2}) = d(x_{1}, v_{2}) = s$. This implies that

Now we claim that $x_{1}\notin V_{3t}$ for otherwise $x_{1}\in V_{1r}\cap V_{2s}\cap V_{3t}$ and $x_{2}\in (V_{1r}\cup V_{1(r+1)})\cap (V_{2s}\cup V_{2(s+1)})\cap (V_{3t}\cup V_{3(t+1)})$. Then by condition (2), for $a = x_{1} = b$ and $c = x_{2}$, $x_{1} = b\nsim c = x_{2}$, which contradicts the assumption that $x = x_{1}x_{2}$ is an edge. Thus

Now consider the edge $y = y_{1}y_{2}$ and again by similar arguments, one of the end points of edge $y$, say, $y_{1}$ is more closer to two of members of $M$ than $y_{2}$. There arise the following sub-cases:

Case 1a:

If $y_{1}$ is more closer to $v_{1}$ and $v_{2}$ as compared to $y_{2}$, then $y_{1}, x_{1}\in V_{1r}\cap V_{2s}$. Again by using condition (2), it can be shown that $y_{2}\in V_{3t}$ and $y_{1}\in V_{3(t+1)}$. But these along with Eq (3.7) imply that $x_{1}, y_{1}\in V_{3(t+1)}$ so that $x_{1}, y_{1}\in V_{1r}\cap V_{2s} \cap V_{3(t+1)}$. This contradicts condition (1).

Case1b:

Now suppose $y_{1}\in V_{3t}$ and $y_{1}$ belong to exactly one of $V_{1r}$ and $V_{2r}$. Without loss of generality assume that $y_{1}\in V_{1r}$. Then

But by using condition (2), we have

Now from Eqs (3.5), (3.6), (3.7), (3.8) and (3.9), we have for $x_{1}, y_{1}\in V_{1r}$, there exists $x_{2}, y_{2}\in (V_{2s}\cup V_{2(s+1)})\cap (V_{3t}\cup V_{3(t+1)})$ such that $x_{1}, y_{2}\in V_{2s}$ and $x_{2}, y_{1}\in V_{3t}$. But then from condition (3), either $x_{1}\nsim x_{2}$ or $y_{1}\nsim y_{2}$, a contradiction.

Case 2:

Suppose the edges $x = x_{1}x_{2}$ and $y_{1}y_{2}$ are adjacent with their common vertex $x_{1} = y_{1}$. Then from (3.4),

We claim that the common vertex $x_{1}$ is nearer to at least two of the vertices of $M$ as compared to other vertices $x_{2}$ and $y_{2}$ for otherwise from (3.10), either $x_{1}\in V_{1(r+1)}\cap V_{2(s+1)}\cap V_{3(t+1)}$ or $x_{1}$ belongs to exactly one of $V_{1r}$, $V_{2s}$ and $V_{3t}$, say $V_{1r}$. If $x_{1}\in V_{1(r+1)}\cap V_{2(s+1)}\cap V_{3(t+1)}$, then from $3.4$, $d(x_{2}, v_{1}) = d(y_{2}, v_{1}) = r$, $d(x_{2}, v_{2}) = d(y_{2}, v_{2}) = s$ and $d(x_{2}, v_{3}) = d(y_{2}, v_{3}) = t$. This further implies that $x_{2}, y_{2}\in V_{1r}\cap V_{2s}\cap V_{3t}$, a contradiction. Also if $x_{1}\in V_{1r}$ but $x_{1}\notin V_{2s}, V_{3t}$, then as from (3.4), $x$ and $y$ are at same distance from $v_{2}$ and $v_{3}$, and from (3.10), the only possibility is

Now we claim that none of $x_{2}$ and $y_{2}$, belongs to $V_{1r}$ for if one of $x_{2}$ and $y_{2}$, say $x_{2}$ belong to $V_{1r}$, then from (3.11), $x_{2}\in V_{1r}\cap V_{2s}\cap V_{3t}$ and $x_{1}, x_{2}\in (V_{1r}\cup V_{1(r+1)})\cap (V_{2s}\cup V_{2(s+1)})\cap (V_{3(t+1)}\cup V_{V_{3t}}$. Using condition (2), $x_{1}\nsim x_{2}$, a contradiction as $x = x_{1}x_{2}$ is an edge. Hence none of $x_{2}$ and $y_{2}$, belongs to $V_{1r}$. Then from (3.10), $x_{2}, y_{2}\in V_{1(r+1)}$. But then $x_{2}, y_{2}\in V_{1(r+1)}\cap V_{2s)}\cap V_{3t}$ which contradicts condition (1). Hence $x_{1}$ is closer to two of the vertices of $M$, say $v_{1}$ and $v_{2}$ as compared to vertices $x_{2}$ and $y_{2}$. Now using condition (2) and (3.10), we can write

Also from (3.10), $x_{2}, y_{2}\in (V_{1r}\cup V_{1(r+1)})\cap(V_{2s}\cup V_{2(s+1)})$. If $x_{2}, y_{2}\in V_{1(r+1)\cap V_{2(s+1)}}$, then this along with (3.12) imply that $x_{2}, y_{2}\in V_{1(r+1)\cap V_{2(s+1)}}\cap V_{3t}$. This contradicts condition (1). Therefore one of $x_{2}$ and $y_{2}$ must belong to one of $V_{1r}$ and $V_{2s}$. Suppose without loss of generality that $x_{2}\in V_{1r}$. Consider $y_{1} = x_{1}, x_{2}\in V_{1r}$, then there exists $x_{1}, y_{2}\in (V_{1r}\cup V_{1(r+1)})\cap (V_{2s}\cup V_{2(s+1)})\cap(V_{3t}\cup V_{3(t+1)})$ such that $y_{1}, x_{1}\in V_{2s}$ and $x_{2}, y_{2}\in V_{3t}$. By condition (3), either $y_{1} = x_{1}\nsim to y_{2}$ or $x_{2}\nsim x_{1}$. This leads to a contradiction as $x = x_{1}x_{2}$ and $y_{1}y_{2} = x_{1}y_{2}$ are edges.

All the possible cases lead to a contradiction. Hence $M$ is a mixed metric generator. Therefore $dim_{m}(G)\leq 3$. As $G\ncong P_{n}$, $dim_{m}\geq 3$. Hence $dim_{m}(G) = 3.$ □

4.   Development of algorithms

In this section, three algorithms are developed for determine whether or not "a tree, unicyclic graph and in general a simple connected graphs has mixed dimension three?". The algorithm for tree to have mixed metric dimension three using Theorem 2.2 and Corollary 1 is given in Algorithm 1.

Theorem 4.1. The complexity of the algorithm to determine a mixed basis of dimension three for a graph $J$ of order $n$ and diameter $D$ is $D^3 (\frac{n(n-1)^{4}(n-2)}{6})$.

Proof. It is noted that the number of sets in any distance partition of $V(J)$ is maximum $\delta$. In the proposed algorithm, three distance partitions of $V(J)$ with respect to three distinct vertices are considered at each step. Each set in one partition is compared with two distinct sets from two other partitions(one from each partition). Thus total number of set comparisons is $D^3 (\frac{n(n-1)(n-2)}{6})$. Moreover, in each comparison of three sets, the element wise comparison is at most $(n-1)^3$. Thus the complexity of the algorithm is $D^3 (\frac{n(n-1)^{4}(n-2)}{6})$. □

Lemma 2.3 and Theorem 2.4 are used to develop an algorithm to find unicyclic graphs having mixed dimension 3. It is given in Algorithm 2.

The Lemma 3.9, Lemma3.1, Theorem 3.10, and Theorem 3.11 provide the criteria to determine whether a simple connected graph has mixed metric dimension 3 or not. If a graph has mixed metric dimension three, then Theorem 3.11 also provide the mixed metric basis for the graph. With the help of these results, an algorithm is developed which determines whether a graph has mixed metric dimension three or not and if it exists then it also finds its mixed basis. The algorithm requires the distance matrix of a simple connected graph which is not a path graph. It results in a mixed basis of dimension three of graph, if exists. Otherwise indicates that graph has mixed metric greater than three.

5.   Conclusions

In this paper, it is shown that the mixed metric dimension of tree $T_{n}\ncong P_{n}$ ($n\geq 3$) is 3 if and only if $T_{n}\cong \Gamma_{P_{t}}(P_{1}, \cdots, P_{1}, P_{r}, P_{1}, \cdots, P_{1})$, where $P_{r}$ is attached to a vertex which is not pendant vertex such that $r\geq2$ and $n = t+r-1$ and $t\geq 3$. For unicycle graph $U_n$, it is proved that $dim_m(U_n) = 3$ if and only if either $U_n\cong C_n$ or $U_{n}\cong \Gamma_{C_{m}}(P_{r}, \underbrace{P_{1}, \cdots, P_{1}}_{m-1\; times})$, where $m+r-1 = n$ (i.e., tadpole graph) or $U_{n}\cong \Gamma_{C_{m}}(P_{r_{1}}, \underbrace{P_{1} \cdots, P_{1}}_{i\; times}, P_{r_{2}},$ $\underbrace{P_{1}, \cdots P_{1}}_{m-2-i\; times})$, where $i\geq 0$ and $m+r_{1}+r_{2}-2 = n$ or $U_{n}\cong \Gamma_{C_{m}}(P_{r_{1}}, \underbrace{P_{1} \cdots, P_{1}}_{i\; times}, P_{r_{2}}, \underbrace{P_{1}, \cdots P_{1}}_{j\; times}, P_{r_{3}},$ $\underbrace{P_{1}, \cdots P_{1}}_{m-i-j-3\; times})$ such that $m+r_{1}+r_{2}+r_{3}-3 = n$ and $i+j+3\geq s$, where $s = m/2+1$ if $m$ is even and $s = (m+1)/2$ otherwise. Moreover, several lemmas related to order of graph, maximum degree of basis elements and distance partite sets of basis elements are presented. These lemmas are then used to find the necessary and sufficient conditions for a graph to have mixed metric dimension 3. Finally, three separate algorithms are developed for tree, unicyclic graphs and in general for simple connected graph $J_{n}\ncong P_{n}$ with $n\geq 3$ to determine "whether these graphs have mixed dimension three or not?". If these graphs have mixed dimension three, then these algorithms provide the mixed basis of input graphs.

Acknowledgments

The authors appreciate the valuable comments and remarks of anonymous referees which helped to greatly improve the quality of the paper. The corresponding author(Muhammad Javaid) is supported by the Higher Education Commission of Pakistan through the National Research Program for Universities (NRPU) Grant NO. $20-16188/NRPU/R$&$D/HEC/2021 2021$.

Conflict of interest

The authors declare that they have no conflicts of interest.