Research article

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

  • Received: 30 January 2024 Revised: 23 February 2024 Accepted: 01 March 2024 Published: 07 March 2024
  • MSC : 05C69

  • 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

    Related Papers:

  • 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
  • Reader Comments
  • © 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(586) PDF downloads(37) Cited by(0)

Article outline

Figures and Tables

Figures(3)

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog