Electronic Notes in Discrete Mathematics 31 (2008), 137-142.
Determining the minimum rank of matroids whose basis graph is common
by Masahiro Hachimori, Hiroshi Kurata, Tadashi Sakuma.
Abstract
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 r_{min}(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 in terms of the distance matrix of G.
By using it, we obtain an O(n^3)-time algorithm to determine r_{min}, where n=|V(G)|,
the number of bases in its corresponding matroid.