On the neighbor-distinguishing in generalized Petersen graphs

Shabbar Naqvi; Muhammad Salman; Muhammad Ehtisham; Muhammad Fazil; Masood Ur Rehman; Shabbar Naqvi; Muhammad Salman; Muhammad Ehtisham; Muhammad Fazil; Masood Ur Rehman

doi:10.3934/math.2021797

AIMS Mathematics

2021, Volume 6, Issue 12: 13734-13745. doi: 10.3934/math.2021797

Previous Article Next Article

Research article Special Issues

On the neighbor-distinguishing in generalized Petersen graphs

1.
Department of Basic Sciences, Balochistan University of Engineering and Technology Khuzdar, 89100, Pakistan
2.
Department of Mathematics, The Islamia University of Bahawalpur, 63100, Pakistan
3.
Department of Mathematics and Statistics, Institute of Southern Punjab Multan, 60800, Pakistan
4.
Department of Basic Sciences and Humanities, Bahauddin Zakariya University Multan, 60800, Pakistan
5.
Department of Mathematics, University College of Zhob, BUITEMS, Zhob 85200, Pakistan

Received: 01 April 2021 Accepted: 15 September 2021 Published: 26 September 2021
MSC : 05C12

In a connected graph $ G $, two adjacent vertices are said to be neighbors of each other. A vertex $ v $ adjacently distinguishes a pair $ (x, y) $ of two neighbors in $ G $ if the number of edges in $ v $-$ x $ geodesic and the number of edges in $ v $-$ y $ geodesic differ by one. A set $ S $ of vertices of $ G $ is a neighbor-distinguishing set for $ G $ if every two neighbors in $ G $ are adjacently distinguished by some element of $ S $. In this paper, we consider two families of generalized Petersen graphs and distinguish every two neighbors in these graphs by investigating their minimum neighbor-distinguishing sets, which are of coordinately two.
- distinguishing set,
- neighbor-distinguishing set,
- generalized Petersen graphs
Citation: Shabbar Naqvi, Muhammad Salman, Muhammad Ehtisham, Muhammad Fazil, Masood Ur Rehman. On the neighbor-distinguishing in generalized Petersen graphs[J]. AIMS Mathematics, 2021, 6(12): 13734-13745. doi: 10.3934/math.2021797

Related Papers:

Abstract

In a connected graph $ G $, two adjacent vertices are said to be neighbors of each other. A vertex $ v $ adjacently distinguishes a pair $ (x, y) $ of two neighbors in $ G $ if the number of edges in $ v $-$ x $ geodesic and the number of edges in $ v $-$ y $ geodesic differ by one. A set $ S $ of vertices of $ G $ is a neighbor-distinguishing set for $ G $ if every two neighbors in $ G $ are adjacently distinguished by some element of $ S $. In this paper, we consider two families of generalized Petersen graphs and distinguish every two neighbors in these graphs by investigating their minimum neighbor-distinguishing sets, which are of coordinately two.

References

[1]	E. R. Albirri, Dafik, I. H. Agustin, R. Adawiyah, R. Alfarisi, R. M. prihandini, The local (adjacency) metric dimension of split related complete graph, J. Phys. Conf. Ser., 1211 (2019), 012015. doi: 10.1088/1742-6596/1352/1/012015
[2]	G. A. Barragán-Ramírez, A. Estrada-Moreno, Y. Ramírez-Cruz, J. A. Rodríguez-Velázquez, The local metric dimension of the Lexicographic products of graphs, B. Malays. Math. Sci. So., 42 (2019), 2481–2496. doi: 10.1007/s40840-018-0611-3
[3]	S. Ahmad, M. A. Chaudhry, I. Javaid, M. Salman, On the metric dimension of generalized Petersen graphs, Quaest. Math., 36 (2013), 421–435. doi: 10.2989/16073606.2013.779957
[4]	G. A. Barragán-Ramírez, J. A. Rodríguez-Velázquez, The local metric dimension of strong product of graphs, Graph. Combinator., 32 (2016), 1263–1278. doi: 10.1007/s00373-015-1653-z
[5]	L. M. Blumenthal, Theory and applications of distance geometry, Oxford University Press, 1953.
[6]	H. Fernau, J. A. Rodríguez-Velázquez, On the (adjacency) metric dimension of carona and strong product graphs and their local varients: Cominational and computational results, Discrete Appl. Math., 236 (2018), 183–202. doi: 10.1016/j.dam.2017.11.019
[7]	F. Harary, R. A. Melter, On the metric dimension of a graph, Ars Combinatoria, 2 (1976), 191–195.
[8]	M. Imran, M. K. Siddiqui, R. Naeem, On the metric dimension of generalized Petersen multigraphs, IEEE Access, 6 (2018), 74328–74338.
[9]	M. Imran, S. U. H. Bokary, 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
[10]	M. Johnson, Browsable structure-activity datasets, In: Advances in Molecular Similarity, JAI Press, 1998.
[11]	M. Johnson, Structure-activity maps for visualizing the graph variables arising in drug design, J. Biopharm. Stat., 3 (1993), 203–236. doi: 10.1080/10543409308835060
[12]	I. Khalid, F. Ali, M. Salman, On the metric index of circulant networks: An algorithmic approach, IEEE Access, 7 (2019), 58595–58601. doi: 10.1109/ACCESS.2019.2914933
[13]	S. Khuller, B. Raghavachari, A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math., 70 (1996), 217–229.
[14]	J. B. Liu, M. F. Nadeem, H. M. A. Siddiqui, W. Nazir, Computing metric dimension of certain families of Toeplitz graphs, IEEE Access, 7 (2019), 126734–126741. doi: 10.1109/ACCESS.2019.2938579
[15]	S. Naz, M. Salman, U. Ali, I. Javaid, S. A. Bokhary, On the Constant Metric Dimension of Generalized Petersen Graphs $P(n, 4)$, Acta Math. Sin., 30 (2014), 1145–1160. doi: 10.1007/s10114-014-2372-8
[16]	F. Okamoto, L. Crosse, B. Phinezy, P. Zhang, Kalamazoo, The local metric dimension of graphs, Math. Bohem., 135 (2010), 239–255. doi: 10.21136/MB.2010.140702
[17]	J. A. Rodríguez-Velázquez, C. G. Gómez, G. A. Barragán-Ramírez, Computing the local metric dimension of a graph from the local metric dimension of primary subgraphs, Int. J. Comput. Math., 92 (2015), 686–693. doi: 10.1080/00207160.2014.918608
[18]	J. A. Rodríguez-Velázquez, G. A. Barragán-Ramírez, C. G. Gómez, On the local metric dimension of corona products of graphs, B. Malays. Math. Sci. So., 39 (2016), 157–173. doi: 10.1007/s40840-015-0283-1
[19]	M. Salman, I. Javaid, M. A. Chaudhary, Minimum fault-tolerent, local and strong metric dimension of graphs, Ars Combinatoria, 138 (2018), 333–353.
[20]	Z. Shao, S. M. Sheikholeslami, P. Wu, J. B. Liu, The metric dimension of some generalized Petersen graphs, Discrete Dyn. Nat. Soc., 2018 (2018), 4531958.
[21]	Z. Shao, P. Wu, E. Zhu, L. Chen, On Metric dimension in Some hex derived networks, Sensors, 19 (2019), 94.
[22]	Z. Shao, H. Jiang, P. Wu, S. Wang, J. Žerovnik, X. Zhang, J. B. Liu, On 2-rainbow domination of generalized Petersen graphs, Discrete Appl. Math., 257 (2019), 370–384 doi: 10.1016/j.dam.2018.10.027
[23]	P. J. Slater, Leaves of trees, Proceeding of the 6th Southeastern Conference on Combinatorics, Graph Theory, and Computing, Congressus Numerantium, 14 (1975), 549–559.
[24]	M. E. Watkins, A theorem on Tait coloring with an application to the generalized Petersen graphs, J. Comb. Theory, 6 (1969), 152–164. doi: 10.1016/S0021-9800(69)80116-X

Reader Comments

Your name:*

Email:*
© 2021 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)