M. Baca, E.T. Baskoro, A.N.M. Salman, S.W. Saputro, D. Suprijanto: The metric dimension of regular bipartite graphs, p.15-28

Abstract:

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 $V_1$ and $V_2,$ with $\vert V_1\vert=\vert V_2\vert=n,$ such that every edge of $G$ joins $V_1$ and $V_2$. 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$.

Key Words: Metric dimension, basis, bipartite graph, regular graph.

2000 Mathematics Subject Classification: Primary: 05C12;
Secondary: 05C15, 05C62.

Download the paper in pdf format here.