The metric dimension of regular bipartite graphs

By S. Saputro, E. Baskoro, A. Salman, D. Suprijanto, Andrej Bača. 2011

61 citations recorded by the source corpus.

A set of vertices W resolves a graph G if every vertex is uniquely determined by its vector of distances to the vertices in W. A metric dimension of G is the minimum cardinality of a resolving set of G. A bipartite graph G(n,n) is a graph whose vertex set V can be partitioned into two subsets V1 and V2, with |V1| = |V2| = n, such that every edge of G joins V1 and V2. The graph G is called k-regular if every vertex of G is adjacent to k other vertices. In this paper, we determine the metric dimension of k-regular bipartite graphs G(n,n) where k = n 1 or k = n 2.

View Paper: https://www.semanticscholar.org/paper/8fbca84766f2884204059e8ba6e8d80f61f92e8a