Abstract
The metric dimension is quite a well-studied graph parameter. Recently, the adjacency metric dimension and the local metric dimension have been introduced. We combine these variants and introduce the local adjacency metric dimension. We show that the (local) metric dimension of the corona product of a graph of order n and some non-trivial graph H equals n times the (local) adjacency metric dimension of H. This strong relation also enables us to infer computational hardness results for computing the (local) metric dimension, based on according hardness results for (local) adjacency metric dimension that we also give.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Bailey, R.F., Meagher, K.: On the metric dimension of Grassmann graphs. Discrete Mathematics & Theoretical Computer Science 13, 97–104 (2011)
Brigham, R.C., Chartrand, G., Dutton, R.D., Zhang, P.: Resolving domination in graphs. Mathematica Bohemica 128(1), 25–36 (2003)
Buczkowski, P.S., Chartrand, G., Poisson, C., Zhang, P.: On k-dimensional graphs and their bases. Periodica Mathematica Hungarica 46(1), 9–15 (2003)
Calabro, C., Impagliazzo, R., Paturi, R.: The complexity of satisfiability of small depth circuits. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol. 5917, pp. 75–85. Springer, Heidelberg (2009)
Charon, I., Hudry, O., Lobstein, A.: Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard. Theoretical Computer Science 290(3), 2109–2120 (2003)
Chartrand, G., Saenpholphat, V., Zhang, P.: The independent resolving number of a graph. Mathematica Bohemica 128(4), 379–393 (2003)
Colbourn, C.J., Slater, P.J., Stewart, L.K.: Locating dominating sets in series parallel networks. Congressus Numerantium 56, 135–162 (1987)
Crowston, R., Gutin, G., Jones, M., Saurabh, S., Yeo, A.: Parameterized study of the test cover problem. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 283–295. Springer, Heidelberg (2012)
Díaz, J., Pottonen, O., Serna, M.J., van Leeuwen, E.J.: On the complexity of metric dimension. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 419–430. Springer, Heidelberg (2012)
Feng, M., Wang, K.: On the metric dimension of bilinear forms graphs. Discrete Mathematics 312(6), 1266–1268 (2012)
Frucht, R., Harary, F.: On the corona of two graphs. Aequationes Mathematicae 4, 322–325 (1970)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)
Guo, J., Wang, K., Li, F.: Metric dimension of some distance-regular graphs. Journal of Combinatorial Optimization, 1–8 (2012)
Gutin, G., Muciaccia, G., Yeo, A.: (non-)existence of polynomial kernels for the test cover problem. Information Processing Letters 113(4), 123–126 (2013)
Hammack, R., Imrich, W., Klavžar, S.: Handbook of product graphs. Discrete Mathematics and its Applications, 2nd edn. CRC Press (2011)
Harary, F., Melter, R.A.: On the metric dimension of a graph. Ars Combinatoria 2, 191–195 (1976)
Hartung, S., Nichterlein, A.: On the parameterized and approximation hardness of metric dimension. In: Proceedings of the 28th IEEE Conference on Computational Complexity (CCC 2013), pp. 266–276. IEEE (2013)
Haynes, T.W., Henning, M.A., Howard, J.: Locating and total dominating sets in trees. Discrete Applied Mathematics 154(8), 1293–1300 (2006)
Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? Journal of Computer and System Sciences 63(4), 512–530 (2001)
Iswadi, H., Baskoro, E.T., Simanjuntak, R.: On the metric dimension of corona product of graphs. Far East Journal of Mathematical Sciences 52(2), 155–170 (2011)
Jannesari, M., Omoomi, B.: The metric dimension of the lexicographic product of graphs. Discrete Mathematics 312(22), 3349–3356 (2012)
Johnson, M.: Structure-activity maps for visualizing the graph variables arising in drug design. Journal of Biopharmaceutical Statistics 3(2), 203–236 (1993), pMID: 8220404
Johnson, M.A.: Browsable structure-activity datasets. In: Carbó-Dorca, R., Mezey, P. (eds.) Advances in Molecular Similarity, pp. 153–170. JAI Press Inc., Stamford (1998)
Karpovsky, M.G., Chakrabarty, K., Levitin, L.B.: On a new class of codes for identifying vertices in graphs. IEEE Transactions on Information Theory 44(2), 599–611 (1998)
Khuller, S., Raghavachari, B., Rosenfeld, A.: Landmarks in graphs. Discrete Applied Mathematics 70, 217–229 (1996)
Laifenfeld, M., Trachtenberg, A.: Identifying codes and covering problems. IEEE Transactions on Information Theory 54(9), 3929–3950 (2008)
Lichtenstein, D.: Planar formulae and their uses. SIAM Journal on Computing 11, 329–343 (1982)
Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the Exponential Time Hypothesis. EATCS Bulletin 105, 41–72 (2011)
Okamoto, F., Phinezy, B., Zhang, P.: The local metric dimension of a graph. Mathematica Bohemica 135(3), 239–255 (2010)
Rodríguez-Velázquez, J.A., Fernau, H.: On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results. Tech. Rep. arXiv:1309.2275 [math.CO], ArXiv.org, Cornell University (2013)
Rodríguez-Velázquez, J.A., Barragán-Ramírez, G.A., Gómez, C.G.: On the local metric dimension of corona product graph (2013) (submitted)
Saputro, S., Simanjuntak, R., Uttunggadewa, S., Assiyatun, H., Baskoro, E., Salman, A., Bača, M.: The metric dimension of the lexicographic product of graphs. Discrete Mathematics 313(9), 1045–1051 (2013)
Slater, P.J.: Leaves of trees. Congressus Numerantium 14, 549–559 (1975)
Suomela, J.: Approximability of identifying codes and locating-dominating codes. Information Processing Letters 103(1), 28–33 (2007)
Yero, I.G., Kuziak, D., Rodríquez-Velázquez, J.A.: On the metric dimension of corona product graphs. Computers & Mathematics with Applications 61(9), 2793–2798 (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Fernau, H., Rodríguez-Velázquez, J.A. (2014). Notions of Metric Dimension of Corona Products: Combinatorial and Computational Results. In: Hirsch, E.A., Kuznetsov, S.O., Pin, JÉ., Vereshchagin, N.K. (eds) Computer Science - Theory and Applications. CSR 2014. Lecture Notes in Computer Science, vol 8476. Springer, Cham. https://doi.org/10.1007/978-3-319-06686-8_12
Download citation
DOI: https://doi.org/10.1007/978-3-319-06686-8_12
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-06685-1
Online ISBN: 978-3-319-06686-8
eBook Packages: Computer ScienceComputer Science (R0)