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.