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

Abstract

Let $ G $ be a connected graph of order $ n $. The representation of a vertex $ v $ of $ G $ with respect to an ordered set $ W = \{w_1, w_2, ..., w_k\} $ is the $ k $-vector $ r(v|W) = (d(v, w_1), d(v, w_2), ..., d(v, w_k)) $, where $ d(v, w_i) $ represents the distance between vertices $ v $ and $ w_i $ for $ 1\leq i\leq k $. An ordered set $ W $ is called a connected local resolving set of $ G $ if distinct adjacent vertices have distinct representations with respect to $ W $, and the subgraph $ \langle W\rangle $ induced by $ W $ is connected. A connected local resolving set of $ G $ of minimum cardinality is a connected local basis of $ G $, and this cardinality is the connected local dimension $ \mathop{\text{cld}}(G) $ of $ G $. Two vertices $ u $ and $ v $ of $ G $ are true twins if $ N[u] = N[v] $. In this paper, we establish a fundamental property of a connected local basis of a connected graph $ G $. We analyze the connected local dimension of a connected graph without a singleton true twin class and explore cases involving singleton true twin classes. Our investigation reveals that a graph of order $ n $ contains at most two non-singleton true twin classes when $ \mathop{\text{cld}}(G) = n-2 $. Essentially, our work contributes to the characterization of graphs with a connected local dimension of $ n-2 $.

Keywords

• representation
• connected local resolving set
• connected local dimension
• true twin graph