Regresar

The metric dimension of regular bipartite graphs

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 <inf>1</inf> and V<inf>2</inf>, with V<inf>1</inf>\ = |V<inf>2</inf>| = n, such that every edge of G joins V<inf>1</inf>and V<inf>2</inf>. 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.