Graph Realizations Constrained by Connected Local Dimensions and Connected Local Bases

Abstract

For an ordered set W = {w1, w2, ⋯, wk} of k distinct vertices in a connected graph G, the representation of a vertex v of G with respect to W is the k-vector r(v|W) = (d(v,w1), d(v,w2), ⋯, d(v,wk)), where d(v,wi) is the distance from v to wifor 1 ≤ i ≤ k. The setW is called a connected local resolving set of G if the representations of every two adjacent vertices of G with respect to W are distinct and the subgraph 〈W〉 induced by W is connected. A connected local resolving set of G of minimum cardinality is a connected local basis of G. The connected local dimension cld(G) of G is the cardinality of a connected local basis of G. In this paper, the connected local dimensions of some well-known graphs are determined. We study the relationship between connected local bases and local bases in a connected graph, and also present some realization results. © 2022 World Scientific and Engineering Academy and Society. All rights reserved.