Determining the minimum rank of matroids whose basis graph is common

A graph G is called a matroid basis graph if it is isomorphic to a simple undirected graph whose vertices are the bases of some matroid and its two distinct vertices are adjacent if and only if the corresponding bases can be transformed into each other by a single-element exchange. Let rmin(G) denote the minimum rank of matroids whose matriod basis graph is G in common. In this note, we show a formula which express this value rmin in terms of the distance matrix of G. By using it, we obtain an O(n3)-time algorithm to determine rmin, where n=|V(G)|, the number of bases in its corresponding matroid.