The Metric Dimension of Some Generalized Petersen Graphs
The distance d(u,v) between two distinct vertices u and v in a graph G is the length of a shortest (u,v)-path in G. For an ordered subset W={w1,w2,…,wk} of vertices and a vertex v in G, the code of v with respect to W is the ordered k-tuple cW(v)=(d(v,w1),d(v,w2),…,d(v,wk)). The set W is a resolving...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2018-01-01
|
| Series: | Discrete Dynamics in Nature and Society |
| Online Access: | http://dx.doi.org/10.1155/2018/4531958 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832549358177878016 |
|---|---|
| author | Zehui Shao S. M. Sheikholeslami Pu Wu Jia-Biao Liu |
| author_facet | Zehui Shao S. M. Sheikholeslami Pu Wu Jia-Biao Liu |
| author_sort | Zehui Shao |
| collection | DOAJ |
| description | The distance d(u,v) between two distinct vertices u and v in a graph G is the length of a shortest (u,v)-path in G. For an ordered subset W={w1,w2,…,wk} of vertices and a vertex v in G, the code of v with respect to W is the ordered k-tuple cW(v)=(d(v,w1),d(v,w2),…,d(v,wk)). The set W is a resolving set for G if every two vertices of G have distinct codes. The metric dimension of G is the minimum cardinality of a resolving set of G. In this paper, we first extend the results of the metric dimension of P(n,3) and P(n,4) and study bounds on the metric dimension of the families of the generalized Petersen graphs P(2k,k) and P(3k,k). The obtained results mean that these families of graphs have constant metric dimension. |
| format | Article |
| id | doaj-art-196fa4a165ea4c66b3491cb6356996b6 |
| institution | Kabale University |
| issn | 1026-0226 1607-887X |
| language | English |
| publishDate | 2018-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Discrete Dynamics in Nature and Society |
| spelling | doaj-art-196fa4a165ea4c66b3491cb6356996b62025-02-03T06:11:29ZengWileyDiscrete Dynamics in Nature and Society1026-02261607-887X2018-01-01201810.1155/2018/45319584531958The Metric Dimension of Some Generalized Petersen GraphsZehui Shao0S. M. Sheikholeslami1Pu Wu2Jia-Biao Liu3Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, ChinaDepartment of Mathematics, Azarbaijan Shahid Madani University, Tabriz, IranInstitute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, ChinaSchool of Mathematics and Physics, Anhui Jianzhu University, Hefei 230601, ChinaThe distance d(u,v) between two distinct vertices u and v in a graph G is the length of a shortest (u,v)-path in G. For an ordered subset W={w1,w2,…,wk} of vertices and a vertex v in G, the code of v with respect to W is the ordered k-tuple cW(v)=(d(v,w1),d(v,w2),…,d(v,wk)). The set W is a resolving set for G if every two vertices of G have distinct codes. The metric dimension of G is the minimum cardinality of a resolving set of G. In this paper, we first extend the results of the metric dimension of P(n,3) and P(n,4) and study bounds on the metric dimension of the families of the generalized Petersen graphs P(2k,k) and P(3k,k). The obtained results mean that these families of graphs have constant metric dimension.http://dx.doi.org/10.1155/2018/4531958 |
| spellingShingle | Zehui Shao S. M. Sheikholeslami Pu Wu Jia-Biao Liu The Metric Dimension of Some Generalized Petersen Graphs Discrete Dynamics in Nature and Society |
| title | The Metric Dimension of Some Generalized Petersen Graphs |
| title_full | The Metric Dimension of Some Generalized Petersen Graphs |
| title_fullStr | The Metric Dimension of Some Generalized Petersen Graphs |
| title_full_unstemmed | The Metric Dimension of Some Generalized Petersen Graphs |
| title_short | The Metric Dimension of Some Generalized Petersen Graphs |
| title_sort | metric dimension of some generalized petersen graphs |
| url | http://dx.doi.org/10.1155/2018/4531958 |
| work_keys_str_mv | AT zehuishao themetricdimensionofsomegeneralizedpetersengraphs AT smsheikholeslami themetricdimensionofsomegeneralizedpetersengraphs AT puwu themetricdimensionofsomegeneralizedpetersengraphs AT jiabiaoliu themetricdimensionofsomegeneralizedpetersengraphs AT zehuishao metricdimensionofsomegeneralizedpetersengraphs AT smsheikholeslami metricdimensionofsomegeneralizedpetersengraphs AT puwu metricdimensionofsomegeneralizedpetersengraphs AT jiabiaoliu metricdimensionofsomegeneralizedpetersengraphs |