Fractional metric dimension of generalized prism graph
DOI:
https://doi.org/10.22199/issn.0717-6279-4722Keywords:
resolving neighborhood, fractional metric dimension, cartesian product, generalized prism graphAbstract
Fractional metric dimension of connected graph $G$ was introduced by Arumugam et al. in [Discrete Math. 312, (2012), 1584-1590] as a natural extension of metric dimension which have many applications in different areas of computer sciences for example optimization, intelligent systems, networking and robot navigation. In this paper fractional metric dimension of generalized prism graph $P_{m}\times C_{n}$ is computed using combinatorial criterion devised by Liu et al. in [ Mathematics, 7(1), (2019), 100].
References
S. Arumugam and V. Mathew, “The fractional metric dimension of graphs”, Discrete Mathematics, vol. 312, no. 9, pp. 1584-1590, 2012. https://doi.org/10.1016/j.disc.2011.05.039
S. Arumugam, V. Mathew and J. Shen, “On the fractional metric dimension of graphs”, Discrete Mathematics, Algorithms and Applications, vol. 5, no. 4, pp. 135-137, 2013. https://doi.org/10.1142/s1793830913500377
Z. Beerliova, F. Eberhard, T. Erlebach, A. Hall, M. Hoffman, M. Mihalak and L. Ram, “Network discovery and verification”, IEEE Journal on Selected Areas in Communications, vol. 24, no. 12, pp. 2168-2181, 2006. https://doi.org/10.1109/jsac.2006.884015
J.C. Bermound, F. Comellas and D.F. Hsu, “Distributed loop computer networks: Survey”, Journal of Parallel and Distributed Computing, vol. 24, no. 1, pp. 2-10, 1995. https://doi.org/10.1006/jpdc.1995.1002
A. Borchert and S. Gosselin, “The metric dimension of circulant graphs and Cayley hyper-graphs”, Utilitas Mathematica, 2015. [On line]. Available: https://bit.ly/3pUqCVs
P.J. Cameron and J.H.V. Lint, Designs, Graphs, Codes and their Links, vol. 22. Cambridge: Cambridge University Press, 1991. https://doi.org/10.1017/CBO9780511623714
G. Chartrand, L. Eroh, M. Johnson and O. R. Oellermann, “Resolvability in graphs and the metric dimension of a graph”, Discrete Applied Mathematics, vol. 105, no. 99-113, pp. 99-113, 2000. https://doi.org/10.1016/s0166-218x(00)00198-0
G. Chartrand and L. Lesniak, Graphs & digraphs, 4th ed., Chapman & Hall/CRC, 2005.
V. Chvátal, “Mastermind”, Combinatorica, vol. 3, pp. 325-329, 1983.
J. Currie and O.R. Oellermann, “The metric dimension and metric independence of graphs”, Journal of Combinatorial Mathematics and Combinatorial Computing, vol. 39, pp. 157-167, 2001.
M. Fehr, S. Gosselin and O.R. Oellermann, “The metric dimension of Cayley digraphs”, Discrete Mathematics, vol. 306, no. 1, pp. 31-41, 2006. https://doi.org/10.1016/j.disc.2005.09.015
M. Feng, Lv Benjian and K. Wang, “On the fractional metric dimensión of graphs”, Discrete Applied Mathematics, vol. 170, pp. 55-63, 2014. https://doi.org/10.1016/j.dam.2014.01.006
M. R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the theory of NP. Completeness. New York: Freeman, 1979.
Hammack, W. Imrich, Klavžar, The handbook of product graphs, 2nd ed. Boca Raton: CRC, 2011.
F. Harary and R. A. Melter, “On the metric dimension of a graph”, Ars Combinatoria, vol. 2, pp. 191-195, 1976.
M. Imran, A. Q. Baig, S.A.U.H. Bokhary and I. Javaid, “On the metric dimension of circulant graphs”, Applied Mathematics Letters, vol. 25, pp. 320-325, 2012. https://doi.org/10.1016/j.aml.2011.09.008
M. Imran, M. K. Siddiqui and R. Naeem, “On the metric dimension of generalized Petersen multigraphs”, IEEE Access, vol. 6, pp. 74328-74338, 2018. https://doi.org/10.1109/access.2018.2883556
I. Javaid, M.T. Rahim and K. Ali, “Families of regular graphs with constant metric dimensión”, Utilitas Mathematica, vol. 75, pp. 21-33, 2008.
K. Liu and N. Abu-Ghazaleh, Virtual coordinate back tracking for void traversal in geographic routing. Lecture Notes in Computer Science, vol. 4104, pp. 46-59. Springer 2006.
J. B. Liu, A. Kashif, T. Rashid and M. Javaid, “Fractional metric dimension of generalized Jahangir graph”, Mathematics, vol. 7, no. 1, 2019. https://doi.org/10.3390/math7010100
S. Khuller, B. Raghavachari and A. Rosenfield, “Landmarks in graphs”, Discrete Applied Mathematics, vol. 70, no. 3, pp. 217-229, 1996. https://doi.org/10.1016/0166-218x(95)00106-2
E. R. Scheinerman and D. H. Ulleman, Fractional graph theory: A Rational approach to the theory of graphs. New York: John Wiley & Sons, 1997.
A. Sebő and E. Tannier, “On metric generators of graphs”, Mathematics of Operations Research, vol. 29, no. 2, pp. 383-393, 2004. https://doi.org/10.1287/moor.1030.0070
H. Shapiro and S. Soderberg, “A combinatory detection problema”, The American Mathematical Monthly, vol. 70, no. 10, pp. 1066-1070, 1963.https://doi.org/10.2307/2312835
P. S. Slater, “Leaves of Trees”, Congressus Numerantium, vol. 14, pp. 549-559, 1975.
P. S. Slater, “Domination and location in acyclic graphs”, Networks, vol. 17, no. 1, pp. 55-64, 1987. https://doi.org/10.1002/net.3230170105
Published
How to Cite
Issue
Section
Copyright (c) 2022 Nosheen Goshi, Sohail Zafar, Tabasam Rashid
This work is licensed under a Creative Commons Attribution 4.0 International License.
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
