Constant Time Calculation of the Metric Dimension of the Join of Path Graphs
Symmetry · 12.03.2023 · 15 (3) · 708
DOI: 10.3390/sym15030708 ↗Kurz gefasst
Fachartikel in der Zeitschrift Symmetry, online erschienen am 12.03.2023. Verfasst von Chuanjun Zhang und 5 weiteren Autor:innen. Die Arbeit wurde bisher 10-mal zitiert (Crossref) und nennt 29 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Natural Science Research Projects of Department of Education of Guizhou Provincial, Basic Research Programs of Guizhou Province, Social Science Research Base Project of Department of Education of Guizhou Provincial.
Abstract (Originalsprache)
The distance between two vertices of a simple connected graph G, denoted as d(u,v), is the length of the shortest path from u to v and is always symmetrical. An ordered subset W=w1,w2,w3,⋯,wk of V(G) is a resolving set for G, if for ∀u,v∈V(G), there exists wi∈W ∋ d(u,wi)≠d(v,wi). A resolving set with minimal cardinality is called the metric basis. The metric dimension of G is the cardinality of metric basis of G and is denoted as dim(G). For the graph G1=(V1,E1,) and G2=(V2,E2), their join is denoted by G1+G2. The vertex set of G1+G2 is V1∪V2 and the edge set is E=E1∪E2∪uv,u∈V1,v∈V2. In this article, we show that the metric dimension of the join of two path graphs is unbounded because of its dependence on the size of the paths. We also provide a general formula to determine this metric dimension. We also develop algorithms to obtain metric dimensions and a metric basis for the join of path graphs, with respect to its symmetries.
Förderung
- Natural Science Research Projects of Department of Education of Guizhou Provincial
- Basic Research Programs of Guizhou Province
- Social Science Research Base Project of Department of Education of Guizhou Provincial
- Education Science Planning Project of Guizhou Province
- Doctoral Program of Guizhou Normal College
Zitieren
APA
Zhang, C., Haidar, G., Khan, M. U. I., Yousafzai, F., Hila, K., & Khan, A. U. I. (2023). Constant Time Calculation of the Metric Dimension of the Join of Path Graphs. Symmetry, 15(3), 708. https://doi.org/10.3390/sym15030708
Vancouver
Zhang C, Haidar G, Khan MUI, Yousafzai F, Hila K, Khan AUI. Constant Time Calculation of the Metric Dimension of the Join of Path Graphs. Symmetry. 2023;15(3):708. doi:10.3390/sym15030708
BibTeX
@article{Zhang2023,
author = {Zhang, Chuanjun and Haidar, Ghulam and Khan, Murad Ul Islam and Yousafzai, Faisal and Hila, Kostaq and Khan, Asad Ul Islam},
title = {Constant Time Calculation of the Metric Dimension of the Join of Path Graphs},
journal = {Symmetry},
year = {2023},
volume = {15},
number = {3},
pages = {708},
doi = {10.3390/sym15030708}
}
EUVIMED