On the Metric Dimension of Generalized Petersen Graphs $P(n,3)$
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909739509612544 |
|---|---|
| author | Gao, Rui Xiao, Yingqing Zhang, Zhanqi |
| author_facet | Gao, Rui Xiao, Yingqing Zhang, Zhanqi |
| contents | The metric dimension of a graph $G$ is defined as the minimum number of vertices in a subset $S\subset V(G)$ such that all other vertices are uniquely determined by their distances to the vertices in $S$, and is denoted by $\dim(G)$. In this paper, we study the metric dimension of generalized Petersen graphs $P(n,3)$. The notions of good and bad vertices, which are introduced in Imran et al. (2014, Ars. Combinatoria 117, 113-130), are instrumental in determining the lower bound of the metric dimension for certain types of graphs. We propose an approach, based on these notions, to determine the lower bound of $\dim(P(n,3))$. Moreover, we shall prove that $\dim(P(n,3))=4$, where $n\equiv2,3,4,5 \,\,(\text{mod}\,\, 6)$ and is sufficiently large. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_12224 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Metric Dimension of Generalized Petersen Graphs $P(n,3)$ Gao, Rui Xiao, Yingqing Zhang, Zhanqi Combinatorics Primary 05C35, Secondary 05C12 The metric dimension of a graph $G$ is defined as the minimum number of vertices in a subset $S\subset V(G)$ such that all other vertices are uniquely determined by their distances to the vertices in $S$, and is denoted by $\dim(G)$. In this paper, we study the metric dimension of generalized Petersen graphs $P(n,3)$. The notions of good and bad vertices, which are introduced in Imran et al. (2014, Ars. Combinatoria 117, 113-130), are instrumental in determining the lower bound of the metric dimension for certain types of graphs. We propose an approach, based on these notions, to determine the lower bound of $\dim(P(n,3))$. Moreover, we shall prove that $\dim(P(n,3))=4$, where $n\equiv2,3,4,5 \,\,(\text{mod}\,\, 6)$ and is sufficiently large. |
| title | On the Metric Dimension of Generalized Petersen Graphs $P(n,3)$ |
| topic | Combinatorics Primary 05C35, Secondary 05C12 |
| url | https://arxiv.org/abs/2508.12224 |