The Metric Dimension of the Join of Paths and Cycles

Document Type


Publication Date



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.