Basis pair graphs of transversal matroids are connected

DOI10.1016/0012-365X(89)90267-7MaRDI QIDQ1114716zbMATH OpenFDO

Authors Martin Farber

Publication date 1989

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(89)90267-7

zbMATH Keywords

basis pair graphmatroidtransversal matroids

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Graph theory (05C99)

Review text

The basis pair graph of a matroid on the ground set S has, as its vertices, ordered triples of the form \((B_ 1,B_ 2,B_ 3)\), where \(B_ 1\) and \(B_ 2\) are disjoint bases and \(B_ 3=S\setminus (B_ 1\cup B_ 2)\). Two such vertices, \((A_ 1,A_ 2,A_ 3)\) and \((B_ 1,B_ 2,B_ 3)\), are adjacent if \((B_ 1,B_ 2,B_ 3)\) can be obtained from \((A_ 1,A_ 2,A_ 3)\) by interchanging two elements of S belonging to different components of \((A_ 1,A_ 2,A_ 3)\). It is known that basis pair graphs of graphic and cographic matroids are connected. We show that this holds for transversal matroids as well.

Recommendations

• The \(e\)-exchange basis graph and matroid connectedness
• scientific article; zbMATH DE number 1547724
• On the basis pair graphs of signed-graphic matroids
• On the basis graph of a matroid of arbitrary cardinality
• The basis graph of a bicolored matroid

Cites work

• A Multiple Exchange Property for Bases
• An Affine Representation for Transversal Geometries
• An exchange theorem for bases of matroids
• An Exchange Theorem for Independence Structures
• Decomposing symmetric exchanges in matroid bases
• Edge‐disjoint spanning trees: A connectedness theorem
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• Matroid basis graphs. I
• Matroid basis graphs. II
• On the Tree Graph of a Matroid
• Some properties of basic families of subsets

Cited in

(16)

• Matroids having the same connectivity function
• Edge-disjoint minimum-weight connected spanning \(k\)-edge subgraphs in a weighted graph: A connectedness theorem
• The \(e\)-exchange basis graph and matroid connectedness
• The basis graph of a bicolored matroid
• Serial exchanges in matroids
• On the basis graph of a matroid of arbitrary cardinality
• When do two planted graphs have the same cotransversal matroid?
• On the basis pair graphs of signed-graphic matroids
• On serial symmetric exchanges of matroid bases
• Weighted exchange distance of basis pairs
• Exchange Distance of Basis Pairs in Split Matroids
• Serial exchanges in random bases
• Bases-cobases graphs and polytopes of matroids
• Reconfiguration of basis pairs in regular matroids
• Hamiltonian connectivity of some base-cobase graphs
• Defining matroids through sequential selection

This page was built for publication: Basis pair graphs of transversal matroids are connected

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1114716)