Matroids with bases as minimal resolving sets of graphs

Abstract

We define an independence system associated with simple graphs. We prove that the independence system is a matroid for certain families of graphs, including trees, with bases as minimal resolving sets. Consequently, the greedy algorithm on the matroid can be used to find the minimum-cost resolving set of weighted graphs, wherein the independent system is a matroid. We also characterize hyperplanes of the matroid for trees and prove that its dual matroid is loop-free.

15 pages, 3 figures