A characterization of the base-matroids of a graphic matroid

Francesco Maffioli, Norma Zagaglia Salvi

Abstract


Let $M = (E, \mathcal{F})$ be a matroid on a set $E$ and $B$ one of its bases. A closed set $\theta \subseteq E$ is saturated with respect to $B$ when $|\theta \cap B | \leq r(\theta)$, where $r(\theta)$ is the rank of $\theta$. The collection of subsets $I$ of $E$ such that $| I \cap \theta| \leq r(\theta)$ for every closed saturated set $\theta$ turns out to be the family of independent sets of a new matroid on $E$, called base-matroid and denoted by $M_B$. In this paper we prove that a graphic matroid $M$, isomorphic to a cycle matroid $M(G)$, is isomorphic to $M_B$, for every base $B$ of $M$, if and only if $M$ is direct sum of uniform graphic matroids or, in equivalent way, if and only if $G$ is disjoint union of cacti. Moreover we characterize simple binary matroids $M$ isomorphic to $M_B$, with respect to an assigned base $B$.

Full Text:

PDF


Contributions to Discrete Mathematics. ISSN: 1715-0868