EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Constant Time Calculation of the Metric Dimension of the Join of Path Graphs

Chuanjun Zhang, Ghulam Haidar, Murad Ul Islam Khan, Faisal Yousafzai, Kostaq Hila, Asad Ul Islam Khan

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →