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 $.
Citation: Supachoke Isariyapalakul, Witsarut Pho-on, Varanoot Khemmani. The true twin classes-based investigation for connected local dimensions of connected graphs[J]. AIMS Mathematics, 2024, 9(4): 9435-9446. doi: 10.3934/math.2024460
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 $.
[1] | A. Ali, G. Chartrand, P. Zhang, Irregularity in graphs, Cham: Springer, 2021. http://dx.doi.org/10.1007/978-3-030-67993-4 |
[2] | G. Chartrand, L. Eroh, M. Johnson, O. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math., 105 (2000), 99–113. http://dx.doi.org/10.1016/S0166-218X(00)00198-0 doi: 10.1016/S0166-218X(00)00198-0 |
[3] | F. Harary, R. A. Melter, On the metric dimension of a graph, Ars Comb., 2 (1976), 191–195. |
[4] | B. Hulme, A. Shiver, P. Slater, FIRE: a subroutine for fire protection network analysis, New Mexico: Sandia National Laboratories, 1981. http://dx.doi.org/10.2172/5313603 |
[5] | B. Hulme, A. Shiver, P. Slater, Computing minimum cost fire protection (PROTECT computer code), New Mexico: Sandia National Laboratories, 1982. |
[6] | B. Hulme, A. Shiver, P. Slater, A boolean algebraic analysis of fire protection, North-Holland Mathematics Studies, 95 (1984), 215–227. http://dx.doi.org/10.1016/S0304-0208(08)72964-5 doi: 10.1016/S0304-0208(08)72964-5 |
[7] | S. Isariyapalakul, V. Khemmani, W. Pho-on, The multibases of symmetric caterpillars, J. Math., 2020 (2020), 5210628. http://dx.doi.org/10.1155/2020/5210628 doi: 10.1155/2020/5210628 |
[8] | S. Isariyapalakul, W. Pho-on, V. Khemmani, Bounds on the connected local dimension of graphs in terms of the marked dimension and the clique number, AKCE Int. J. Graphs Co., 19 (2022), 95–101. http://dx.doi.org/10.1080/09728600.2022.2066490 doi: 10.1080/09728600.2022.2066490 |
[9] | M. Johnson, Browsable structure-activity datasets, Advances in Molecular Similarity, 2 (1998), 153–170. |
[10] | V. Khemmani, S. Isariyapalakul, The multiresolving sets of graphs with prescribed multisimilar equivalence classes, International Journal of Mathematics and Mathematical Sciences, 2018 (2018), 8978193. http://dx.doi.org/10.1155/2018/8978193 doi: 10.1155/2018/8978193 |
[11] | V. Khemmani, S. Isariyapalakul, The characterization of caterpillars with multidimension 3, Thai J. Mat., 2020 (2020), 247–259. |
[12] | V. Khemmani, W. Pho-on, S. Isariyapalakul, Graph realizations constrained by connected local dimensions and connected local bases, WSEAS Transactions on Mathematics, 21 (2022), 1–8. http://dx.doi.org/10.37394/23206.2022.21.1 doi: 10.37394/23206.2022.21.1 |
[13] | S. Khuller, B. Rsghavachari, A. Rosenfeld, Localization in graphs, Proeedings of Technical Reports from UMIACS, 1994, 1–11. |
[14] | F. Okamoto, B. Phinezy, P. Zhang, The local metric dimension of a graph, Math. Bohem., 135 (2010), 239–255. http://dx.doi.org/10.21136/MB.2010.140702 doi: 10.21136/MB.2010.140702 |
[15] | V. Saenpholphat, P. Zhang, Connected resolvability of graphs, Czech. Math. J., 53 (2003), 827–840. http://dx.doi.org/10.1023/B:CMAJ.0000024524.43125.cd doi: 10.1023/B:CMAJ.0000024524.43125.cd |
[16] | P. Slater, Leaves of trees, Congressus Numerantium, 14 (1975), 549–559. |
[17] | J. Wang, L. Miao, Y. Liu, Characterization of $n$-vertex graphs of metric dimension $n-3$ by metric matrix, Mathematics, 7 (2019), 479. http://dx.doi.org/10.3390/math7050479 doi: 10.3390/math7050479 |