Acta mathematica scientia, Series B >
ON CLASSES OF REGULAR GRAPHS WITH CONSTANT METRIC DIMENSION
Received date: 2011-09-05
Online published: 2013-01-20
Supported by
This research is partially supported by National University of Sceinces and Technology (NUST), Islamabad, and grant of Higher Education Commission of Pakistan Ref. No: PM-IPFP/HRD/HEC/2011/3386 and support of Slovak VEGA Grant 1/0130/12.
In this paper, we are dealing with the study of the metric dimension of some classes of regular graphs by considering a class of bridgeless cubic graphs called the flower snarks Jn, a class of cubic convex polytopes considering the open problem raised in [M. Imran et al., families of plane graphs with constant metric dimension, Utilitas Math., in press] and finally Harary graphs H5,n by partially answering to an open problem proposed in [I. Javaid et al., Families of regular graphs with constant metric dimension, Utilitas Math., 2012, 88: 43–57]. We prove that these classes of regular graphs have constant metric dimension.
Key words： metric dimension; basis; resolving set; cubic graph; flower snark; convex polytope
Muhammad IMRAN , Syed Ahtsham ul Haq BOKHARY , Ali AHMAD , Andrea SEMANICOVá-FE?OVCíKOVá . ON CLASSES OF REGULAR GRAPHS WITH CONSTANT METRIC DIMENSION[J]. Acta mathematica scientia, Series B, 2013 , 33(1) : 187 -206 . DOI: 10.1016/S0252-9602(12)60204-5
[1] Buczkowski P S, Chartrand G, Poisson C, Zhang P. On k-dimensional graphs and their bases. Periodica Math Hung, 2003, 46(1): 9–15
[2] Caceres J, Garijo D, Puertas M L, Seara C. On the mdetermining number and the metric dimension of graphs. Electronic J Combin, 2010, 17: R63
[3] Caceres J, Hernando C, Mora M, Pelayo I M, Puertas M L, Seara C, Wood D R. On the metric dimension of cartesian product of graphs. SIAM J Disc Math, 2007, 2(21): 423–441
[4] Caceres J, Hernando C, Mora M, Pelayo I M, Puertas M L, Seara C, Wood D R. On the metric dimension of some families of graphs. Electronic Notes in Disc Math, 2005, 22: 129–133
[5] Cameron P J, Van Lint J H. Designs, Graphs, Codes and Their Links. London Mathematical Society Student Texts 22, Cambridge: Cambridge University Press, 1991
[6] Chartrand G, Eroh L, Johnson M A, Oellermann O R. Resolvability in graphs and metric dimension of a graph. Disc Appl Math, 2000, 105: 99–113
[7] Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: Freeman, 1979
[8] Harary F. The maximum connectivity of a graph. Proc Nat Acad Sci USA, 1962, 48: 1142–1146
[9] Hernando C, Mora M, Pelayo I M, Seara C, Wood D R. Extremal graph theory for metric dimension and diameter. Electronic J Combin, 2010, 17(1): R30
[10] Imran M, Baig A Q, Ahmad A. Families of plane graphs with constant metric dimension. Utilitas Math, 2012, 88: 43–57
[11] Imran M, Baig A Q, Shafiq M K, Tomescu I. On metric dimension of generalized Petersen graphs P(n, 3). Ars Combin, in press
[12] Isaacs R. Infinite families of nontrivial trivalent graphs which are not Tait colorable. Amer Math Monthly, 1975, 82: 221–239
[13] Javaid I, Rahim M T, Ali K. Families of regular graphs with constant metric dimension. Utilitas Math, 2008, 75: 21–33
[14] Jucoviˇc E. Convex Polyhedra. Bratislava: Veda, 1981
[15] Khuller S, Raghavachari B, Rosenfeld A. Landmarks in graphs. Disc Appl Math, 1996, 70: 217–229
[16] Melter R A, Tomescu I. Metric bases in digital geometry. Computer Vision, Graphics and Image Processing, 1984, 25: 113–121
[17] Miller M, Baˇca M, MacDougall J A. Vertex-magic total labelling of generalized Petersen graphs and convex polytopes. JCMCC, 2006, 59: 89–99
[18] Oellermann O R, Peters-Fransen J. The strong metric dimension of graphs and digraphs. Disc Appl Math, 2007, 155: 356–364
[19] Slater P J. Leaves of trees. Congress Numer, 1975, 14: 549–559
[20] Slater P J. Dominating and reference sets in graphs. J Math Phys Sci, 1998, 22: 445–455
[21] Sudhakara G, Hemanth Kumar A R. Graphs with Metric Dimension Two-A Characterization. WASET, 2009, 60
[22] Tomescu I, Javaid I. On the metric dimension of the Jahangir graph. Bull Math Soc Sci Math Roumanie, 2007, 50(98): 371–376
[23] Yero I G, Kuziak D, Rodr´?guez-Vel´azquez J A. On the metric dimension of a corona product graphs. Comput Math Appl, 2011, 61(9): 2793–2798
/
| 〈 |
|
〉 |