Cyclic orderings and cyclic arboricity of matroids

DOI10.1016/J.JCTB.2011.08.004zbMATH Open1241.05060arXiv0912.2929OpenAlexW2020928988MaRDI QIDQ414636FDOQ414636

Stéphan Thomassé, Jan van den Heuvel

Publication date: 11 May 2012

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: We prove a general result concerning cyclic orderings of the elements of a matroid. For each matroid $M$, weight function $omega:E(M)ightarrowmathbbN$, and positive integer $D$, the following are equivalent. (1) For all $AsubseteqE(M)$, we have $su{m}_{ainA}omega(a)leDcdotr(A)$. (2) There is a map $phi$ that assigns to each element $e$ of $E(M)$ a set $phi(e)$ of $omega(e)$ cyclically consecutive elements in the cycle $(1,2,\mathrm{...},D)$ so that each set $e|iinphi(e)$, for $i=1,\mathrm{...},D$, is independent. As a first corollary we obtain the following. For each matroid $M$ so that $|E(M)|$ and $r(M)$ are coprime, the following are equivalent. (1) For all non-empty $AsubseteqE(M)$, we have $|A|/r(A)le|E(M)|/r(M)$. (2) There is a cyclic permutation of $E(M)$ in which all sets of $r(M)$ cyclically consecutive elements are bases of $M$. A second corollary is that the circular arboricity of a matroid is equal to its fractional arboricity. These results generalise classical results of Edmonds, Nash-Williams and Tutte on covering and packing matroids by bases and graphs by spanning trees.

Full work available at URL: https://arxiv.org/abs/0912.2929

Recommendations

• Equicovering matroids by distinct bases
• Circuit and fractional circuit covers of matroids
• Cyclic Matroids
• Matroids with a cyclic arrangement of circuits and cocircuits
• Cycle cover ratio of regular matroids

zbMATH Keywords

arboricitymatroidbase of a matroidcircular arboricitycyclic ordering

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Paths and cycles (05C38) Combinatorial aspects of packing and covering (05B40)

Cites Work

• Title not available (Why is that?)
• On the Problem of Decomposing a Graph into n Connected Factors
• Edge-Disjoint Spanning Trees of Finite Graphs
• Decomposition of Finite Graphs Into Forests
• Title not available (Why is that?)
• Minimum partition of a matroid into independent subsets
• Title not available (Why is that?)
• Circular chromatic number: A survey
• Fractional arboricity, strength, and principal partitions in graphs and matroids
• Ordering of the elements of a matroid such that its consecutive w elements are independent
• Equicovering matroids by distinct bases
• Decomposing symmetric exchanges in matroid bases
• Lehmans switching game and a theorem of Tutte and Nash-Williams
• Bases-cobases graphs and polytopes of matroids

Cited In (12)

• Exchange Distance of Basis Pairs in Split Matroids
• On Sequential Basis Exchange in Matroids
• On Serial Symmetric Exchanges of Matroid Bases
• On a base exchange game on bispanning graphs
• On the Complexity of Digraph Colourings and Vertex Arboricity
• Cycle cover ratio of regular matroids
• Ordering of the elements of a matroid such that its consecutive w elements are independent
• Cyclic orderings of paving matroids
• Non-preemptive tree packing
• Title not available (Why is that?)
• Cyclic base ordering of generalized Petersen graphs
• Cyclic base ordering of certain degenerate graphs

This page was built for publication: Cyclic orderings and cyclic arboricity of matroids

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