#### Title

The Metric Dimension of the Join of Paths and Cycles

#### Document Type

Article

#### Publication Date

10-29-2021

#### Abstract

For an ordered subset W={w1,w2,…,wk}">W={w1,w2,…,wk}W={w1,w2,…,wk} of vertices in a connected graph *G* and a vertex *v* of *G*, the metric representation of *v* with respect to *W* is the *k*-vector r(v|W)=(d(v,w1),…,d(v,wk))">r(v|W)=(d(v,w1),…,d(v,wk))r(v|W)=(d(v,w1),…,d(v,wk)), where d(v,wi)">d(v,wi)d(v,wi) is the distance of the vertices *v* and wi">wiwi in *G*. The set *W* is called a resolving set of *G* if r(u|W)=r(v|W)">r(u|W)=r(v|W)r(u|W)=r(v|W) implies u=v">u=vu=v. A resolving set of *G* with minimum cardinality is called a metric basis of *G*. The metric dimension of *G*, denoted by β(G)">β(G)β(G), is the cardinality of a metric basis of *G*.

The *join* of *G* and *H*, denoted by G+H">G+HG+H, is the graph with vertex set V(G+H)=V(G)∪V(H)">V(G+H)=V(G)∪V(H)V(G+H)=V(G)∪V(H) and edge set E(G+H)=E(G)∪E(H)∪{uv:u∈V(G),v∈V(H)}">E(G+H)=E(G)∪E(H)∪{uv:u∈V(G),v∈V(H)}E(G+H)=E(G)∪E(H)∪{uv:u∈V(G),v∈V(H)}. In general, the join of *m* graphs G1,G2,…,Gm">G1,G2,…,GmG1,G2,…,Gm, denoted by G=G1+G2+⋯+Gm">G=G1+G2+⋯+GmG=G1+G2+⋯+Gm, has vertex set V(G)=V(G1)∪V(G2)∪⋯∪V(Gm)">V(G)=V(G1)∪V(G2)∪⋯∪V(Gm)V(G)=V(G1)∪V(G2)∪⋯∪V(Gm) and edge set E(G)=E(G1)∪E(G2)∪⋯∪E(Gm)∪{uv:u∈Gi,v∈Gj,i≠j}">E(G)=E(G1)∪E(G2)∪⋯∪E(Gm)∪{uv:u∈Gi,v∈Gj,i≠j}E(G)=E(G1)∪E(G2)∪⋯∪E(Gm)∪{uv:u∈Gi,v∈Gj,i≠j}.

In this paper, we compute the metric dimension of the join of a finite number of paths, the join of a finite number of cycles, and the join of paths and cycles.

#### Recommended Citation

Garces, I. J. L., & Rosario, J. B. (2021). The metric dimension of the join of paths and cycles. In J. Akiyama, R. M. Marcelo, M.-J. P. Ruiz, & Y. Uno (Eds.), Discrete and Computational Geometry, Graphs, and Games (pp. 43–58). Springer International Publishing. https://doi.org/10.1007/978-3-030-90048-9_5