Research article

On the metric basis in wheels with consecutive missing spokes

  • Received: 05 April 2020 Accepted: 23 July 2020 Published: 31 July 2020
  • MSC : 05C12

  • If $G$ is a connected graph, the $distance$ $d(u, v)$ between two vertices $u, v \in V(G)$ is the length of a shortest path between them. Let $W = \{w_1, w_2, \dots, w_k\}$ be an ordered set of vertices of $G$ and let $v$ be a vertex of $G$. The $representation$ $r(v|W)$ of $v$ with respect to $W$ is the k-tuple $(d(v, w_1), d(v, w_2), \dots, d(v, w_k))$. $W$ is called a resolving set or a locating set if every vertex of $G$ is uniquely identified by its distances from the vertices of $W$, or equivalently if distinct vertices of $G$ have distinct representations with respect to $W$. A resolving set of minimum cardinality is called a metric basis for $G$ and this cardinality is the metric dimension of $G$, denoted by $\beta(G)$. The metric dimension of some wheel related graphs is studied recently by Siddiqui and Imran. In this paper, we study the metric dimension of wheels with $k$ consecutive missing spokes denoted by $W(n, k)$. We compute the exact value of the metric dimension of $W(n, k)$ which shows that wheels with consecutive missing spokes have unbounded metric dimensions. It is natural to ask for the characterization of graphs with an unbounded metric dimension. The exchange property for resolving a set of $W(n, k)$ has also been studied in this paper and it is shown that exchange property of the bases in a vector space does not hold for minimal resolving sets of wheels with $k$-consecutive missing spokes denoted by $W(n, k)$.

    Citation: Syed Ahtsham Ul Haq Bokhary, Zill-e-Shams, Abdul Ghaffar, Kottakkaran Sooppy Nisar. On the metric basis in wheels with consecutive missing spokes[J]. AIMS Mathematics, 2020, 5(6): 6221-6232. doi: 10.3934/math.2020400

    Related Papers:

  • If $G$ is a connected graph, the $distance$ $d(u, v)$ between two vertices $u, v \in V(G)$ is the length of a shortest path between them. Let $W = \{w_1, w_2, \dots, w_k\}$ be an ordered set of vertices of $G$ and let $v$ be a vertex of $G$. The $representation$ $r(v|W)$ of $v$ with respect to $W$ is the k-tuple $(d(v, w_1), d(v, w_2), \dots, d(v, w_k))$. $W$ is called a resolving set or a locating set if every vertex of $G$ is uniquely identified by its distances from the vertices of $W$, or equivalently if distinct vertices of $G$ have distinct representations with respect to $W$. A resolving set of minimum cardinality is called a metric basis for $G$ and this cardinality is the metric dimension of $G$, denoted by $\beta(G)$. The metric dimension of some wheel related graphs is studied recently by Siddiqui and Imran. In this paper, we study the metric dimension of wheels with $k$ consecutive missing spokes denoted by $W(n, k)$. We compute the exact value of the metric dimension of $W(n, k)$ which shows that wheels with consecutive missing spokes have unbounded metric dimensions. It is natural to ask for the characterization of graphs with an unbounded metric dimension. The exchange property for resolving a set of $W(n, k)$ has also been studied in this paper and it is shown that exchange property of the bases in a vector space does not hold for minimal resolving sets of wheels with $k$-consecutive missing spokes denoted by $W(n, k)$.


    加载中


    [1] G. Abbas, U. Ali, M. Munir, et al. Power graphs and exchange property for resolving sets, Open Math., 17 (2019), 1303-1309. doi: 10.1515/math-2019-0093
    [2] D. L. Boutin, Determining sets, resolving sets and the exchange property, Graphs Combin., 25 (2009), 789-806. doi: 10.1007/s00373-010-0880-6
    [3] P. S. Buczkowski, G. Chartrand, C. Poisson, et al. On k-dimensional graphs and their bases, Periodica Math. Hung., 46 (2003), 9-15. doi: 10.1023/A:1025745406160
    [4] J. Caceres, C. Hernando, M. Mora, et al. On the metric dimension of cartesian product of graphs, SIAM J. Disc. Math., 2 (2007), 423-441.
    [5] P. J. Cameron, J. H. Van Lint, Designs, Graphs, Codes and their Links, London Mathematical Society Student Texts 22, Cambridge University Press, Cambridge, 1991.
    [6] G. Chartrand, L. Eroh, M. A. Johnson, et al. Resolvability in graphs and metric dimension of a graph, Disc. Appl. Math., 105 (2000), 99-113. doi: 10.1016/S0166-218X(00)00198-0
    [7] F. M. Dong, Y. P. Liu, All wheels with two missing consecutive spokes are chromatically unique, Disc. Math., 184 (1998), 71-85. doi: 10.1016/S0012-365X(96)00288-9
    [8] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP- Completeness, Freeman, New York, 1979.
    [9] F. Harary, R. A. Melter, On the metric dimension of a graph, Ars Combin., 2 (1976), 191-195.
    [10] M. Imran, A. Q. Baig, M. K. Shafiq, et al. On metric dimension of generlized Petersen graphs P(n, 3), Ars Combin., 117 (2014), 113-130.
    [11] M. Imran, A. Q. Baig, S. A. Bokhary, et al. On the metric dimension of circulant graphs, Appl. Math. Lett., 25 (2012), 320-325. doi: 10.1016/j.aml.2011.09.008
    [12] M. Imran, S. A. Bokhary, A. Q. Baig, On families of convex polytopes with constant metric dimension, Comput. Math. Appl., 60 (2010), 2629-2638. doi: 10.1016/j.camwa.2010.08.090
    [13] M. Imran, A. Ahmad, S. A. Bokhary, et al. On classes of regular graphs with constant metric dimension, Acta Math. Scientia, 33 (2013), 187-206. doi: 10.1016/S0252-9602(12)60204-5
    [14] M. Imran, H. M. A. Siddiqui, Computing the metric dimension of convex polytopes generated by wheel related graphs, Acta Math. Hungar., 149 (2016), 10-30. doi: 10.1007/s10474-016-0606-1
    [15] I. Javaid, M. T. Rahim, K. Ali, Families of regular graphs with constant metric dimension, Utilitas Math., 75 (2008), 21-33.
    [16] S. Khuller, B. Raghavachari, A. Rosenfeld, Landmarks in graphs, Disc. Appl. Math., 70 (1996), 217-229. doi: 10.1016/0166-218X(95)00106-2
    [17] S. Khuller, B. Raghavachari, A. Rosenfeld, Localization in graphs, Technical Report CS-TR-3326, University of Maryland at College Park, 1994.
    [18] R. A. Melter, I. Tomescu, Metric bases in digital geometry, Comput. Vision Graphics, Image Processing, 25 (1984), 113-121. doi: 10.1016/0734-189X(84)90051-3
    [19] O. R. Oellermann, J. Peters-Fransen, Metric dimension of Cartesian products of graphs, Utilitas Math., 69 (2006), 33-41.
    [20] M. Salman, I. Javaid, M. A. Chaudhry, Resolvability in circulant graphs, Acta Math. Sin. Engl. Ser., 28 (2012), 1851-1864. doi: 10.1007/s10114-012-0417-4
    [21] A. Sebö, E. Tannier, On metric generators of graphs, Math. Oper. Res., 29(2004),383-393. doi: 10.1287/moor.1030.0070
    [22] H. M. A. Siddiqui, M. Imran, Computing the metric dimension of wheel related graphs, Appl. Math. Comput., 242 (2014), 624-632.
    [23] P. J. Slater, Leaves of trees, Congress. Numer., 14 (1975), 549-559.
    [24] P. J. Slater, Dominating and reference sets in graphs, J. Math. Phys. Sci., 22 (1988), 445-455.
    [25] I. Tomescu, M. Imran, On metric and partition dimensions of some infinite regular graphs, Bull. Math. Soc. Sci. Math. Roumanie, 52 (2009), 461-472.
    [26] I. Tomescu, I. Javaid, On the metric dimension of the Jahangir graph, Bull. Math. Soc. Sci. Math. Roumanie, 50 (2007), 371-376.
    [27] U. Ali, S. A. Bokhary, K. Wahid, et al. On resolvability of a graph associated to a finite vector space, Journal of Algebra and Its Applications, 18 (2018), 1950028.
  • Reader Comments
  • © 2020 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(2841) PDF downloads(197) Cited by(0)

Article outline

Figures and Tables

Figures(3)

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog