The true twin classes-based investigation for connected local dimensions of connected graphs

1.   Introduction

For vertices $u$ and $v$ in a connected graph $G$, the distance $d(u, v)$ between $u$ and $v$ is the length of the shortest $u-v$ path in $G$. A $u-v$ path of length $d(u, v)$ is called a $u-v$ geodesic. Let $W = \{w_1, w_2, ..., w_k\}$ be an ordered set of vertices in $G$. The representation of $v$ with respect to $W$ is the $k$-vector $r(v|W) = (d(v, w_1), d(v, w_2), ..., d(v, w_k))$. If the representations of any two distinct vertices in $G$ with respect to $W$ are distinct, then $W$ is called a resolving set of $G$. A minimal cardinality resolving set is referred to as a minimum resolving set or a basis of $G$, and this cardinality is referred to as the dimension of $G$, which is denoted by $\dim(G)$.

The concept of a resolving set of a connected graph $G$ was introduced by Slater in ^[16]. The usefulness of the concept was mentioned in ^[4,5,6]. Similar concepts were also discovered independently; see ^[3,9]. The connected graphs of order $n$ with dimension $n-2$ and $n-3$ were characterized in ^[2,17], respectively. The concept of the resolving set lies within the theme of irregularity of graphs; see ^[1]. Further studies and applications of resolving sets were presented in ^[7,10,11,13].

Some interesting developments in the concept of resolving sets are locality and connectivity. For any two adjacent vertices $u$ and $v$ of $G$, if $r(u|W)\neq r(v|W)$, then $W$ is called a local resolving set of $G$. A minimum cardinality local resolving set is called a minimum local resolving set or a local basis of $G$, and this cardinality is said to be the local dimension $\text{ld}(G)$ of $G$. For connectivity, a resolving set $W$ of $G$ is called a connected resolving set of $G$ if the induced subgraph $\langle W\rangle$ is connected. The minimum cardinality of a connected resolving set of $G$ is the connected dimension $\text{cd}(G)$ of $G$, and a resolving set of $G$ having this cardinality is called a minimum connected resolving set or a connected basis of $G$. To illustrate these concepts, consider the graph $G$ of Figure 1. For an ordered set $W_1 = \{u, z\}$, the representations of vertices of $G$ with respect to $W_1$ are

Hence, $W_1$ is a local resolving set of $G$ since any two adjacent vertices of $G$ have distinct representations with respect to $W_1$. However, $W_1$ is not a resolving set. Since $G$ contains no local resolving set of cardinality $1$, it follows that $W_1$ is a local basis of $G$, and so $\text{ld}(G) = 2$. For an ordered set $W_2 = \{u, x\}$, the representations of vertices of $G$ with respect to $W_2$ are

We can see that $W_2$ is a resolving set of $G$. However, since $\langle W_2\rangle$ is not connected, it follows that $W_2$ is not a connected resolving set of $G$. The idea of a local resolving set was introduced by Okamoto and others in ^[14]. They characterized all nontrivial connected graphs of order $n$ with local dimensions $1$, $n$$-1$, and $n-2$. The concept of a connected resolving set has been described in ^[15], and the term connected resolving number has been used to denote what we have referred to as the connected dimension.

The two developments mentioned above lead us to study a local resolving set $W$ of a connected graph $G$ with the property that the induced subgraph $\langle W\rangle$ is connected in $G$. An ordered set $W$ of vertices of a connected graph $G$ is said to be a connected local resolving set of $G$ if $W$ is a local resolving set of $G$ and the induced subgraph $\langle W\rangle$ of $G$ is connected. A minimal cardinality connected local resolving set of $G$ is called a minimum connected local resolving set or a connected local basis of $G$. The cardinality of a connected local basis of $G$ is the connected local dimension, denoted by $\text{cld}(G)$.

Consider the graph $G$ in Figure 1. Observe that $W_1 = \{u, z\}$ is a local resolving set, but it is not a connected local resolving set. For an ordered set $W_3 = \{u, w, z\}$, the representations of vertices in $G$ with respect to $W_3$ are

Since the representations of two adjacent vertices are distinct, and $\langle W_3\rangle = P_3$ is connected, it follows that $W_3$ is a connected local resolving set of $G$. Through a case-by-case analysis, it can be shown that $W_3$ is also a connected local basis of $G$, and thus $\mathop{\text{cld}}(G) = 3$. Connected local resolving sets were further studied in ^[8,12].

Note that every connected local resolving set of $G$ is a local resolving set of $G$, but the converse is not true in general. Furthermore, every connected resolving set of $G$ is a connected local resolving set of $G$. Nevertheless, not every connected local resolving set of $G$ is necessarily a connected resolving set of $G$. Therefore, we have arrived at the following:

In fact, a characterization of local metric dimensions 1, $n - 2$, and $n - 1$ in a nontrivial connected graph of order $n$ was established in ^[14]. Additionally, all connected graphs $G$ of order $n \geq 2$ with $\text{cd}(G) = 1$, $n - 1$ were characterized in ^[15].

For every ordered set $W = \mathop{\{w_1, w_2, \dots, w_k\}}$ of vertices of a connected graph $G$, the only vertex of $G$ whose representation with respect to $W$ contains $0$ in its $i^\text{th}$ coordinate is $w_i$. Therefore, the vertices of $W$ necessarily have distinct representations with respect to $W$. Furthermore, the representations of vertices of $G$ that do not belong to $W$ have coordinates, all of which are positive. Indeed, to determine whether an ordered set $W$ is a connected local resolving set of $G$, we only need to verify that any two adjacent vertices in $V(G)-W$ have distinct representations with respect to $W$, and $\langle W\rangle$ is connected.

2.   Connected local dimension with prescribed true twin classes

First, we present a principal property of a connected local basis of a connected graph $G$. We then recall that a vertex $v$ of a connected graph $G$ is a cut-vertex of $G$ if $G-v$ is not connected. Furthermore, a set $U$ of vertices of $G$ is called a vertex-cut if $G-U$ is not connected.

Proposition 2.1. Let $W$ be a connected local basis of a connected graph $G$. Then, every vertex $v$ of $W$ satisfies at least one of the following conditions:

(ⅰ)$\langle W-\{v\}\rangle$ is not connected, or

(ⅱ) there are two adjacent vertices $x$ and $y$ in $V(G)-(W-\{v\})$ such that $d(x, w) = d(y, w)$ for all vertices $w\in W-\{v\}$.

Proof. Let $v$ be a vertex of a connected local basis of a connected graph $G$. If $v$ is a cut-vertex of $\langle W\rangle$, then (ⅰ) holds. Assume that $v$ is not a cut-vertex of $\langle W\rangle$. Then, $v$ does not satisfy (ⅰ). Hence, $\langle W-\{v\}\rangle$ is connected. Since $W$ is a connected local basis of $G$, it follows that $\langle W-\{v\}\rangle$ is not a local resolving set of $G$. In other words, there exist two adjacent vertices $x$ and $y$ in $G$ such that $r(x|W-\{v\}) = r(y|W-\{v\})$. This implies that $d(x, w) = d(y, w)$ for all $w\in W-\{v\}$. □

The open neighborhood, or simply the neighborhood, of a vertex $u$ of a connected graph $G$ is defined as the set of all vertices that are adjacent to $u$, which is denoted by $N(u) = \{v\in V(G)\; |\; uv\in E(G)\}$. The closed neighborhood $N[u]$ of $u$ is defined as $N(u)\cup \{u\}$. Two vertices $u$ and $v$ of $G$ are true twins if $N[u] = N[v]$. Observe that the true twin relation is an equivalence relation on $V(G)$, and as such, this relation partitions $V(G)$ into equivalence classes, which are called the true twin equivalence classes or simply the true twin classes on $V(G)$. Observe that if $G$ contains $l$ distinct true twin classes $U_1, U_2, ..., U_l$, then every local resolving set of $G$ must contain at least $|U_i|-1$ vertices from $U_i$ for each integer $i$ with $1\leq i\leq l$. This observation was presented in ^[14] as follows.

Proposition 2.2. ^[14] Let $G$ be a connected graph having $l$ true twin classes $U_1, U_2, ..., U_l$. Then, every local resolving set of $G$ must contain every vertex, except at most one, in each true twin class $U_i$, where $1\leq i\leq l$. Moreover, $\textrm{ld}(G)\geq \sum\limits_{i = 1}^{l}|U_i|-l$.

The following result which appeared in ^[14] will be useful to us.

Theorem 2.1. ^[14] If $G$ is a nontrivial connected graph of order $n$ with $l$ true twin classes, none of which is a singleton set, then $\textrm{ld}(G) = n-l$.

The following theorem provides the connected local dimension of a connected graph that does not have a singleton true twin class.

Theorem 2.2. If $G$ is a connected graph of order $n$ with $l$ true twin classes, none of which is a singleton set, then $\textrm{cld}(G) = n-l$.

Proof. By Theorem 2.1, it follows that $\mathop{\text{ld}}(G) = n-l$. Consequently, by (1), $\mathop{\text{cld}}(G)\geq n-l$. Next, we show that there exists a connected local resolving set of $G$ having cardinality $n-l$. In order to do this, let $W$ be a local basis of $G$. By Proposition 2.2 and Theorem 2.1, $W = V(G)-\{u_1, u_2, ..., u_l\}$, where $u_1, u_2, ..., u_l$ belong to distinct true twin classes, resulting in $|W| = n-l$. We claim that $\langle W\rangle$ is connected. Let $x$ and $y$ represent two distinct vertices of $W$. Since $G$ is connected, it follows that there is an $x-y$ path $P$ in $G$. If $V(P)\subseteq W$, then $x$ and $y$ are connected in $\langle W\rangle$. We therefore assume that $V(P)\nsubseteq W$. Then, $V(P)$ contains $u_i$ for some integer $i$ with $1\leq i\leq l$. Since $G$ contains only non-singleton true twin classes, there is a vertex $v_i$ such that $v_i$ and $u_i$ belong to the same true twin class. We construct an $x-y$ path $Q$ from $P$ by replacing $u_i$ with $v_i$. If $V(Q)\subseteq W$, then $x$ and $y$ are connected in $\langle W\rangle$. If this is not the case, we continue the above procedure until finally arriving at $x$ and $y$ are connected in $\langle W\rangle$. Consequently, $W$ is a connected local resolving set of $G$, that is, $\text{cld}(G)\leq n-l$. Thus, $\mathop{\text{cld}}(G) = n-l$. □

If a connected graph $G$ contains some singleton true twin classes, then vertices in these true twin classes may or may not be in a connected local resolving set of $G$. Next, we investigate the connected local dimension of $G$ having some singleton true twin classes. To do that, we first establish a definition. Let $G$ be a connected graph containing at least two true twin classes. For two distinct true twin classes $U$ and $V$ of $G$, define the true twin distance $d(U, V)$ between $U$ and $V$ by $d(U, V) = d(u, v)$, where $u\in U$ and $v\in V$. Observe that $d(U, V)\geq 1$. Next, we present a useful lemma.

Lemma 2.1. Let $G$ be a connected graph having $l$ true twin classes, and $d(U, V) = l-1$ for some true twin classes $U$ and $V$ of $G$. Then, for each $u\in U$ and $v\in V$, every $u-v$ geodesic contains exactly one vertex from each true twin class. Furthermore, every $u-v$ path contains at least one vertex from each true twin class.

Proof. Let $U$ and $V$ be distinct true twin classes of $G$ with $d(U, V) = l-1$, and let $u\in U$ and $v\in V$. Consider a $u-v$ geodesic $P = (u = u_1, u_2, ..., u_l = v)$ in $G$. Suppose that $P$ contains two vertices $u_i$ and $u_j$ from the same true twin class for some integer $i, j$ with $1\leq i < j\leq l$. If $u_j\neq u_l$, then deleting the vertices $u_{i+1}, u_{i+2}, ..., u_j$ from $P$ yields the $u-v$ path $(u = u_1, u_2, ..., u_i, u_{j+1}, ..., u_l = v)$ with length less than $l-1$, which is impossible. If $u_j = u_l$, then deleting the vertices $u_{i}, u_{i+1}, ..., u_{j-1}$ from $P$ yields the $u-v$ path $(u = u_1, u_2, ..., u_{i-1}, u_j = u_l = v)$ with length less than $l-1$, which is also impossible. Thus, no two vertices of $P$ belong to the same true twin class. Since $P$ contains $l$ vertices, it follows that $P$ contains exactly one vertex from each true twin class.

Next, let $P' = (u = u'_1, u'_2, ..., u'_k = v)$ be a $u-v$ path of length $k-1\geq l-1$. Assume that there is a true twin class $U'$ of $G$ such that every vertex in $U'$ does not lie on $P'$. If $P'$ contains two vertices $u'_i$ and $u'_j$ from the same true twin class for some integer $i, j$ with $1\leq i < j\leq k$, then, as in the case of $P$, we delete the vertices $u'_{i+1}, u'_{i+2}, ..., u'_j$ or $u'_{i}, u'_{i+1}, ..., u'_{j-1}$ from $P'$, arriving at a $u-v$ path with length less than $k-1$. If there are two vertices of this $u-v$ path belonging to the same true twin class, we continue the procedure until arriving at a $u-v$ path, $Q'$, such that no two of its vertices belong to the same true twin class. Since $Q'$ contains no vertices of $U'$, the length of $Q'$ is less than $l-1$, which is a contradiction. Hence, $P'$ contains at least one vertex from each true twin class. □

We are now prepared to present the connected local dimension of a connected graph containing some singleton true twin classes.

Theorem 2.3. Let $G$ be a connected graph having $l$ true twin classes, and $d(U, V) = l-1$ for some non-singleton true twin classes $U$ and $V$ of $G$. If there are $p$ singleton true twin classes of $G$, then $\textrm{cld}(G) = n-l+p$.

Proof. Let $p$ be the number of singleton true twin classes in $G$. Then, $1\leq p\leq l-2$. Let $U_1, U_2, ..., U_l$ be true twin classes of $G$, where $|U_i|\geq 2$ for $1\leq i\leq l-p$ and $|U_i| = 1$ for $l-p+1\leq i\leq l$, and let $u_i\in U_i$ for $1\leq i\leq l$. First, we show that $W = V(G)-\{u_1, u_2, ..., u_{l-p}\}$ is a connected local resolving set of $G$. Let $u_i$ and $u_j$ be adjacent vertices in $V(G)-W$, where $1\leq i < j\leq l-p$. As $u_i$ and $u_j$ belong to distinct true twin equivalence classes, there exists a vertex $v\in W$ that is adjacent to either $u_i$ or $u_j$, but not both, say $u_i$. Consequently, $d(u_i, v) = 1 < 2 = d(u_j, v)$, implying that $W$ is a local resolving set of $G$. We now claim that $\langle W\rangle$ is connected. Let $x$ and $y$ be vertices of $W$. Since $G$ is connected, it follows that there is an $x-y$ path $P$ in $G$. If $P$ contains no $u_i$ for $1\leq i\leq l-p$, then $\langle W\rangle$ is connected. If $P$ contains some vertices $u_i$ for $1\leq i\leq l-p$, then an $x-y$ path $Q$ is obtained from $P$ by replacing each $u_i$ by $v_i$, where $v_i$ is a vertex of $U_i$ for $1\leq i\leq l-p$. Thus, $\langle W\rangle$ is connected, and so $W$ is a connected local resolving set of $G$. Therefore, $\mathop{\text{cld}}(G)\leq n-l+p$. To demonstrate $\mathop{\text{cld}}(G)\geq n-l+p$, let $W'$ be a connected local resolving set of $G$. Since $d(U, V) = l-1$ for some non-singleton true twin classes $U$ and $V$ of $G$, there exists a $u-v$ path $P'$ of length $l-1$, where $u\in U$ and $v\in V$. By Lemma 2.1, $P'$ contains exactly one vertex from each true twin class. Consequently, $W'$ must contain $u_i\in U_i$ for $l-p+1\leq i\leq l$. Since $|U_i|\geq 2$ for $1\leq i\leq l-p$, $W'$ must include at least $|U_i|-1$ vertices from $U_i$ for $1\leq i\leq l-p$. Therefore, $|W'|\geq n-l+p$, that is, $\mathop{\text{cld}}(G)\geq n-l+p$. Hence, $\mathop{\text{cld}}(G) = n-l+p$. □

3.   The characterization of connected graphs with connected local dimension $n-2$

Consider a connected graph $G$ with $l$ distinct true twin classes denoted as $U_1, U_2, ..., U_l$. The true twin graph $tG$ of $G$ is defined as a graph having a vertex set $\{U_1, U_2, ..., U_l\}$. In $tG$, two distinct vertices $U_i$ and $U_j$ are adjacent if and only if $d(U_i, U_j) = 1$ (in $G$), where $1\leq i < j\leq l$. Actually, if each of the true twin classes of $G$ consists of a single vertex, then $tG = G$.

For example, the connected graph $G$ given in Figure 2(a) has eight true twin classes $U_1 = \{u_1\}$, $U_2 = \{u_2, u_{10}\}$, $U_3 = \{u_3\}$, $U_4 = \{u_4\}$, $U_5 = \{u_5\}$, $U_6 = \{u_6, u_7\}$, $U_7 = \{u_8\}$, and $U_8 = \{u_9\}$. Then, the true twin graph $tG$ has the vertex set $\{U_1, U_2, ..., U_8\}$, and this true twin graph is shown in Figure 2(b).

Let $u$ and $v$ be vertices of a connected graph $G$ belonging to distinct true twin classes. Then, $N[u]\neq N[v]$, and so there is a vertex $w$ of $G$ that is adjacent to either $u$ or $v$, but not both. This concept leads to the following useful result.

Lemma 3.1. Let $x$, $y$, and $z$ be vertices belonging to distinct true twin classes of a connected graph $G$. Assume that $G-\{x, y, z\}$ is connected. If

(ⅰ) $\langle \{x, y, z\}\rangle = K_3$,

(ⅱ) $\langle \{x, y, z\}\rangle = (x, y, z)$, a path of order 3, where $x$ and $z$ belong to non-singleton true twin classes,

(ⅲ) $\langle \{x, y, z\}\rangle = K_2\cup K_1$, or

(ⅳ) $\langle \{x, y, z\}\rangle = \overline{K_3}$,

then $V(G)-\{x, y, z\}$ is a connected local resolving set of $G$.

Proof. Let $W = V(G)-\{x, y, z\}$. Since $G-\{x, y, z\}$ is connected, it remains to prove that $W$ is a local resolving set of $G$.

(ⅰ) Assume that $\langle \{x, y, z\}\rangle = K_3$. For any distinct $u, v\in \{x, y, z\}$, since $u$ and $v$ belong to distinct true twin classes, there exists a vertex $w$ of $W$ that is adjacent to either $u$ or $v$, but not both. Consequently, $r(u|W)\neq r(v|W)$, and hence $W$ is a local resolving set of $G$.

(ⅱ) Assume that $\langle \{x, y, z\}\rangle = P_3 = (x, y, z)$, where $x$ and $z$ belong to non-singleton true twin classes. Then, there are two vertices $x'$ and $z'$ such that both $x$ and $x'$ belong to the same true twin class and both $z$ and $z'$ belong to the same true twin class. Since $d(x, z') = 2 > 1 = d(y, z')$ and $d(z, x') = 2 > 1 = d(y, x')$, $r(x|W)\neq r(y|W)$ and $r(z|W)\neq r(y|W)$, respectively. Therefore, $W$ is a local resolving set of $G$.

(ⅲ) Assume that $\langle \{x, y, z\}\rangle = K_2\cup K_1$. Without loss of generality, let $V(K_2) = \{x, y\}$, and $V(K_1) = \{z\}$. Since $x$ and $y$ belong to distinct true twin classes, there is a vertex $w$ of $W$ such that $w$ is adjacent to either $x$ or $y$, but not both. Therefore, $r(x|W)\neq r(y|W)$, implying that $W$ is a local resolving set of $G$.

(ⅳ) Assume that $\langle \{x, y, z\}\rangle = \overline{K_3}$. Since $\{x, y, z\}$ is independent, it follows that $W$ is a local resolving set of $G$. □

As we mentioned earlier, every connected local resolving set of a connected graph $G$ must contain at least $|U|-1$ vertices from $U$, where $U$ is a true twin class of $G$. This implies that a connected graph $G$ of order $n$ contains at most two non-singleton true twin classes if $\mathop{\text{cld}}(G) = n-2$, as we present next.

Theorem 3.1. Let $G$ be a connected graph of order $n$. If $\textrm{cld}(G) = n-2$, then $G$ contains at most two non-singleton true twin classes.

Proof. Suppose, to the contrary, that there are three non-singleton true twin classes denoted as $U_1$, $U_2$, and $U_3$. For $1\leq i\leq 3$, let $u_i\in U_i$. Observe that $G-\{u_1, u_2, u_3\}$ is connected. There are four possibilities of each induced subgraph $\langle \{u_1, u_2, u_3\}\rangle$ of $G$: $\langle \{u_1, u_2, u_3\}\rangle = K_3$, $\langle \{u_1, u_2, u_3\}\rangle = P_3$, $\langle \{u_1, u_2, u_3\}\rangle = K_2\cup K_1$, or $\langle \{u_1, u_2, u_3\}\rangle = \overline{K_3}$. That $V(G)-\{u_1, u_2, u_3\}$ is a connected local resolving set of $G$ is an immediate consequence of Lemma 3.1. Therefore, $\mathop{\text{cld}}(G)\leq n-3$, which contradicts the fact that $\mathop{\text{cld}}(G) = n-2$. □

Theorem 3.1 gives a necessary condition for a connected graph $G$ of order $n$ with $\text{cld}(G) = n-2$. However, a connected graph $G$ of order $n$ containing at most two non-singleton true twin classes is not a sufficient condition for a graph $G$ having $\text{cld}(G) = n-2$. For example, when $n\geq 4$, a path $P_n$ contains no non-singleton true twin class, but $\text{cld}(P_n) = 1 \neq n-2$. Furthermore, Theorem 3.1 provides an important point for investigating a connected graph $G$ of order $n$ with the connected local dimension $n-2$. To characterize all such graphs $G$, it suffices to consider connected graphs containing at most two non-singleton true twin classes. We first present the characterization of connected graphs $G$ of order $n$ that do not contain non-singleton true twin classes satisfying $\mathop{\text{cld}}(G) = n-2$.

Theorem 3.2. Let $G$ be a connected graph of order $n$ containing no non-singleton true twin class. Then, $\textrm{cld}(G) = n-2$ if and only if $tG = P_3$.

Proof. If $tG = P_3$, then $G = P_3$ since $G$ contains only singleton true twin classes. It can be shown that $\mathop{\text{cld}}(P_3) = 1$. To verify the converse, assume that $\mathop{\text{cld}}(G) = n-2$. For $n = 3$, only the graph $G = P_3$ has the desired property. For $n = 4$, all connected graphs of order $4$ having only singleton true twin classes are $P_4$, $K_{1, 3}$, and $C_4$. It is routine to verify that all of them have connected local dimensions of $1$. This implies that there is no connected graph of order $4$ with the connected local dimension $2$. We therefore assume that $n\geq 5$. Then, there are three vertices $x$, $y$, and $z$ of $G$ such that $G-\{x, y, z\}$ is connected. Let $W = \{x, y, z\}$. If $\langle W\rangle = K_3$, $\langle W\rangle = K_2\cup K_1$, or $\langle W\rangle = \overline{K_3}$, then $V(G)-W$ is a connected local resolving set of $G$ by Lemma 3.1(ⅰ), (ⅲ), and (ⅳ), respectively. Therefore, $\mathop{\text{cld}}(G)\leq n-3$, which contradicts the fact that $\mathop{\text{cld}}(G) = n-2$. Assume that $\langle W\rangle = P_3 = (x, y, z)$. Since $\mathop{\text{cld}}(G) = n-2$, it follows that $V(G)-W$ is not a local resolving set of $G$. Thus, we may assume, without loss of generality, that $r(x|W) = r(y|W)$. Then, $N[x] = N[y]-\{z\}$. Let $G' = G-\{x, y\}$. We consider two cases.

Case 1. $z$ is adjacent to some vertex in $G'$.

Since $G'$ is connected, it follows that there is a vertex $u\neq z$ in $G'$ such that $G'-u$ is connected. Thus, $G-\{x, y, u\}$ is connected. We observe that the induced subgraph $\langle \{x, y, u\}\rangle$ of $G$ is either $K_3$ or $K_2\cup K_1$. Nevertheless, $\langle \{x, y, u\}\rangle$ is a connected local resolving set of $G$ by Lemma 3.1(ⅰ) and (ⅲ), respectively. Therefore, $\mathop{\text{cld}}(G)\leq n-3$, establishing a contradiction.

Case 2. $z$ is not adjacent to every vertex in $G'$.

Since $G$ is connected and $N[x] = N[y]-\{z\}$, it follows that there is a vertex in $G'-z$ that is adjacent to both $x$ and $y$, so $G-\{x, z\}$ remains connected. Thus, there is a vertex $v\neq y$ in $G-\{x, z\}$ such that $G-\{x, z, v\}$ is connected. We now obtain that the induced subgraph $\langle \{x, z, v\}\rangle$ of $G$ is either $K_2\cup K_1$ or $\overline{K_3}$. However, $\langle \{x, z, v\}\rangle$ is a connected local resolving set of $G$ by Lemma 3.1(ⅲ) and (ⅳ), respectively. Thus, $\mathop{\text{cld}}(G)\leq n-3$, which is impossible.

Hence, for $n\geq 5$, there is no connected graph $G$ of order $n$ containing only singleton true twin classes such that $\mathop{\text{cld}}(G) = n-2$. This implies that $G = tG = P_3$. □

Next, we will identify all connected graphs $G$ of order $n$ containing exactly one non-singleton true twin class such that $\mathop{\text{cld}}(G) = n-2$. To do this, we first introduce some key notation. The eccentricity $e(u)$ of a vertex $u$ in a connected graph $G$ is the distance between $u$ and a vertex farthest from $u$ in $G$. The following lemma is useful.

Lemma 3.2. Let $G$ be a connected graph of order $n$ containing exactly one non-singleton true twin class $U$. If $\textrm{cld}(G) = n-2$, then $e(u)\leq 2$, where $u\in U$.

Proof. Assume, to the contrary, that $e(u)\geq 3$. Then, there is a vertex $v$ of $G$ such that $d(u, v) = k = e(u)\geq 3$. Let $(u = u_0, u_1, u_2, ..., u_k = v)$ be a $u-v$ geodesic in $G$. For the set $V(G)-\{u, u_{k-1}, u_k\}$, if $G-\{u, u_{k-1}, u_k\}$ is connected, then $V(G)-\{u, u_{k-1}, u_k\}$ is a connected local resolving set of $G$, and so $\mathop{\text{cld}}(G)\leq n-3$, contradicting the fact that $\mathop{\text{cld}}(G) = n-2$. Assume that $G-\{u, u_{k-1}, u_k\}$ is not connected. In other words, $\{u, u_{k-1}, u_k\}$ is a vertex-cut. Since $u$ belongs to a non-singleton true twin class, $\{u_{k-1}, u_k\}$ is also a vertex-cut. Let $G_1$ be a component of $G-\{u_{k-1}, u_k\}$ that contains $u$. We claim that every vertex $x\in V(G)-(V(G_1)\cup\{u_{k-1}, u_k\})$ is adjacent to $u_{k-1}$ in $G$. Suppose, contrary to our claim, that such a vertex $x$ is not adjacent to $u_{k-1}$ in $G$. Consequently, there exists a $u-x$ geodesic in $G$ containing $u_1, u_2, ..., u_{k-1}, u_k$. This implies that $G$ contains a $u-x$ path of length at least $k+1$, which contradicts the fact that $e(u) = k$. Hence, every vertex $x\in V(G)-(V(G_1)\cup\{u_{k-1}, u_k\})$ is adjacent to $u_{k-1}$. Therefore, $G-\{u, x, u_k\}$ is connected. Since the induced subgraph $\langle \{u, x, u_k\}\rangle$ of $G$ is either $K_2\cup K_1$ or $\overline{K_3}$, it follows by Lemma 3.1(ⅲ) and (ⅳ) that $V(G)-\{u, x, u_k\}$ is a connected local resolving set of $G$, that is, $\mathop{\text{cld}}(G)\leq n-3$, which is impossible. Thus, $e(u)\leq 2$. □

Theorem 3.3. Let $G$ be a connected graph of order $n$ containing exactly one non-singleton true twin class. Then, $\textrm{cld}(G) = n-2$ if and only if $tG = P_3$.

Proof. Assume that the true twin graph $tG$ of $G$ is the path $P_3 = (X, Y, Z)$. Since $G$ contains three true twin classes, it follows by Proposition 2.2 that $\mathop{\text{ld}}(G)\geq n-3$, and so $\mathop{\text{cld}}(G)\geq n-3$. If either $X$ or $Z$ is a non-singleton true twin class of $G$, say $X$, then $X$ is a connected local resolving set of $G$, that is, $\mathop{\text{cld}}(G)\leq n-2$. Indeed, $G$ contains no connected local resolving set of cardinality $n-3$. Otherwise, a connected local resolving set $W$ of $G$ consists of $|X|-1$ vertices of $X$. This implies that there are two vertices $x$ and $y$, where $x\in X-W$ and $y\in Y$ with $r(x|W) = r(y|W)$, which is impossible. If $Y$ is a non-singleton true twin class of $G$, then $Y$ is a connected local resolving set of $G$, and so $\mathop{\text{cld}}(G)\leq n-2$. Similarly, $G$ contains no connected resolving set of cardinality $n-3$. Therefore, $\mathop{\text{cld}}(G) = n-2$. Conversely, assume that $\mathop{\text{cld}}(G) = n-2$. Let $U$ be the non-singleton true twin class of $G$. For a vertex $u$ in $U$, we have that $e(u)\leq 2$ by Lemma 3.2. We therefore consider two cases according to the eccentricity of $u$.

Case 1. $e(u) = 1$.

Since $G$ is not complete, and $U$ is the only non-singleton true twin class of $G$, it follows that there are at least two vertices $x$ and $y$ that do not belong to $U$. Since $e(u) = 1$, it follows that $u$ is adjacent to both $x$ and $y$. We claim that $|V(G)-U| = 2$. Suppose, contrary to our claim, that there are at least three vertices of $V(G)-U$. Then, there are two adjacent vertices in $G-U$. Otherwise, there is a set $S$ of three independent vertices in $V(G)-U$ such that $G-S$ is connected, and $\langle S\rangle = \overline{K_3}$. By Lemma 3.1(ⅳ), $S$ is a connected local resolving set of $G$, that is, $\mathop{\text{cld}}(G)\leq n-3$, a contradiction. Let $x$ and $y$ be two adjacent vertices in $G-U$. Since $G-\{u, x, y\}$ is connected, and $\langle \{u, x, y\}\rangle = K_3$, it follows by Lemma 3.1(ⅰ) that $\{u, x, y\}$ is a connected local resolving set of $G$, and so $\mathop{\text{cld}}(G) \leq n-3$, which is impossible. Thus, as claimed, $|V(G)-U| = 2$. Since the two vertices in $V(G)-U$ are not true twins, it follows that $|V(tG)| = 3$, and so $tG = P_3$.

Case 2. $e(u) = 2$.

Then, there is a vertex $v\notin U$ with $d(u, v) = 2$. Let $(u, x, v)$ be a $u-v$ geodesic in $G$. We first prove the following claim.

Claim. Every vertex in $V(G)-(U\cup \{x, v\})$ must be adjacent to $u$.

Suppose, contrary to our claim, that there is a vertex $z\in V(G)-(U\cup \{x, v\})$ that is not adjacent to $u$. Then, $d(u, z) = 2$, that is, $G-\{v, z\}$ is connected, so is $G-\{u, v, z\}$. Since the induced subgraph $\langle \{u, v, z\}\rangle$ is either $K_2\cup K_1$ or $\overline{K_3}$, it follows by Lemma 3.1(ⅲ) and (ⅳ) that $V(G)-\{u, v, z\}$ is a connected local resolving set of $G$, which is impossible. Thus, every vertex in $V(G)-(U\cup \{x, v\})$ must be adjacent to $u$.

Next, we show that $V(G)-U = \{x, v\}$. Assume, to the contrary, that there is a vertex $z\in V(G)-(U\cup \{x, v\})$. By the claim, we obtain that $z$ is adjacent to $u$. If $x$ is not adjacent to $z$, then $V(G)-\{u, v, z\}$ is a connected local resolving set of $G$. This is a contradiction. Thus, $x$ and $z$ are adjacent. Assume that $z$ is not adjacent to $v$. Since $\langle \{u, v, z\}\rangle = K_2\cup K_1$, it follows by Lemma 3.1(ⅲ) that $V(G)-\{u, v, z\}$ is a connected local resolving set of $G$, producing a contradiction. Therefore, $z$ is adjacent to $v$. Since $\langle \{v, x, z\}\rangle = K_3$, it follows by Lemma 3.1(ⅰ) that $V(G)-\{v, x, z\}$ is a connected local resolving set of $G$. This is a contradiction. Hence, $V(G)-U = \{x, v\}$. Since $x$ and $v$ are not true twins, it follows that $|V(tG)| = 3$, and hence $tG = P_3$. □

Last, we investigate all connected graphs $G$ containing two non-singleton true twin classes such that $\mathop{\text{cld}}(G) = n-2$.

Theorem 3.4. Let $G$ be a connected graph of order $n$ containing exactly two non-singleton true twin classes. Then, $\textrm{cld}(G) = n-2$ if and only if

where $U$ and $V$ are two distinct non-singleton true twin classes of $G$.

Proof. For $k\geq 2$, if $tG = P_{k+1}$, then $G$ has $k+1$ true twin classes. Since $U$ and $V$ are non-singleton true twin classes and $d(U, V) = k$, it follows by Theorem 2.3 that $\mathop{\text{cld}}(G) = n-2$. For $d(U, V) = 1$, if $tG = P_3$, then $G$ has three true twin classes. Without loss of generality, consider $tG = (U, V, \{x\})$ and let $u\in U$ and $v\in V$. Since $G$ contains no connected local resolving set of cardinality $n-3$, it follows that $\mathop{\text{cld}}(G)\geq n-2$. It can be shown that $V(G)-\{u, v\}$ is a connected local resolving set of $G$. This implies that $\mathop{\text{cld}}(G) = n-2$. We now verify the converse. Assume that $\mathop{\text{cld}}(G) = n-2$. Let $u\in U$ and $v\in V$. We consider two cases.

Case 1. $d(U, V) = 1$.

Since $u$ and $v$ are not true twins, it follows that there is a vertex $x\in V(G)-(U\cup V)$ such that $x$ is adjacent to every vertex in either $U$ or $V$, but not both, say $V$. We claim that $G$ have only three true twin classes $U$, $V$, and $\{x\}$. Suppose, contrary to our claim, that $G$ contains another true twin class. If $e(v) = 1$, then there is a vertex $y\in V(G)-(U\cup V\cup \{x\})$ that is adjacent to $v$. Since every vertex in $G$ is adjacent to $v$, it follows that $G-y$ is connected, and so is $G-\{u, v, y\}$. Since $u$, $v$, and $y$ are not true twins, it follows that $V(G)-\{u, v, y\}$ is a connected local resolving set of $G$ and so $\mathop{\text{cld}}(G)\leq n-3$, contradicting the fact that $\mathop{\text{cld}}(G) = n-2$. We may assume that $e(v)\geq 2$. Then, there is a vertex $z\in V(G)-(U\cup V\cup \{x\})$ with $d(v, z) = e(v)\geq 2$. Notice that $G-\{u, v, z\}$ is connected. Thus, $V(G)-\{u, v, z\}$ is a connected local resolving set of $G$, and so $\mathop{\text{cld}}(G)\leq n-3$, which is impossible. Hence, $G$ has only three true twin classes $U$, $V$, and $\{x\}$, that is, $tG = P_3$.

Case 2. $d(U, V) = k\geq 2$.

Let $P = (u = u_0, u_1, ..., u_k = v)$ be a $u-v$ geodesic of $G$. Then, every internal vertex of $P$ belongs to a singleton true twin class. We claim that $V(G)-(U\cup V) = \{u_1, u_2, ..., u_{k-1}\}$. Suppose, contrary to our claim, that there is a vertex $x$ in $V(G)-(U\cup V\cup V(P))$. We consider two subcases.

Subcase 2.1. Neither $u$ nor $v$ is adjacent to $x$.

If $x$ is not a cut-vertex of $G$, then $G-\{u, v, x\}$ is connected. Since $\langle \{u, v, x\}\rangle = \overline{K_3}$, it follows by Lemma 3.1(ⅳ) that $V(G)-\{u, v, x\}$ is a connected local resolving set of $G$, producing a contradiction. We may assume that $x$ is a cut-vertex of $G$. Then, there are at least two components $G_1$ and $G_2$ of $G-x$. Suppose that $G_1$ contains $U$ and $V$. Thus, there is a vertex $x'$ of $G_2$ such that $G-x'$ is connected, that is, $G-\{u, v, x'\}$ is also connected. Since $\langle \{u, v, x'\}\rangle = \overline{K_3}$, it follows that $V(G)-\{u, v, x'\}$ is a connected local resolving set of $G$, which is impossible.

Subcase 2.2. Either $u$ or $v$ is adjacent to $x$, say $u$.

Similarly, if $x$ is not a cut-vertex of $G$, then $G-\{u, v, x\}$ is connected. Since $\langle \{u, v, x\}\rangle$ is $K_2\cup K_1$ or $P_3$, it follows by Lemma 3.1(ⅱ) and (ⅲ), respectively, that $V(G)-\{u, v, x\}$ is a connected local resolving set of $G$. This is a contradiction. We therefore assume that $x$ is a cut-vertex of $G$. Thus, there is a vertex $x'$ in a component of $G-x$ not containing $U$ and $V$ such that $G-\{u, v, x'\}$ is connected. Observe that $\langle \{u, v, x'\}\rangle = \overline{K_3}$. Consequently, $V(G)-\{u, v, x'\}$ is a connected local resolving set of $G$ by Lemma 3.1(ⅳ). This is also a contradiction.

Hence, as claimed, $V(G)-(U\cup V) = \{u_1, u_2, ..., u_{k-1}\}$, and so $tG = P_{k+1}$. □

All connected graphs of order $n$ with connected local dimension $n-2$ are characterized by Theorems 3.2–3.4. The following result is a consequence of these theorems.

Corollary 3.1. Let $G$ be a connected graph of order $n$. Then, $\textrm{cld}(G) = n-2$ if and only if one of the following holds:

(ⅰ) $tG = P_3$, and $G$ contains at most two non-singleton true twin classes.

(ⅱ) $tG = P_{k+1}$, and $G$ contains exactly two non-singleton true twin classes $U$ and $V$, with $d(U, V) = k\geq 3.$

Some examples of graphs with connected local dimension $n - 2$ are shown in Figure 3. Vertices in the same non-singleton true twin class in each graph are enclosed by a dashed circle. The true twin graphs of the graphs $G_1$ and $G_2$ are $P_3$, as seen Figure 3(a) and (b). In Figure 3(c), the true twin graph of the graph $G_3$ is $P_5$, and the distance between the two non-singleton true twin classes of $G_3$ is 4.

4.   Conclusions

In this paper, we have established a principal property of a connected local basis of a connected graph $G$. In our analysis, we determined that for a connected graph $G$ of order $n$ with $l$ true twin classes, none of which is a singleton set, the connected local dimension is given by $\mathop{\text{cld}}(G) = n - l$. Extending our investigation to involve a connected graph $G$ with $l$ true twin classes and $d(U, V) = l-1$ for some non-singleton true twin classes $U$ and $V$ of $G$, and if there are $p$ singleton true twin classes in $G$, then $\mathop{\text{cld}}(G) = n - l + p$. We demonstrated that, in a connected graph $G$ of order $n$ with a connected local dimension $\mathop{\text{cld}}(G) = n -2$, there exist at most two non-singleton true twin classes. Ultimately, our research significantly contributes to the characterization of graphs with a connected local dimension of $n - 2$.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgements

This work was funded by the Faculty of Science, Srinakharinwirot University (202/2565).

Conflict of interest

The authors declare that they have no conflicts of interest.