Good orientations of unions of edge-disjoint spanning trees

Jørgen Bang-Jensen*, Stéphane Bessy, Jing Huang, Matthias Kriesell

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

In this paper, we exhibit connections between the following subjects: Tree packing in graphs and digraphs (both behave completely different), the rigidity matroid of a graph, Henneberg moves on trees, the conjectures of Thomassen and Matthews and Sumner, and (s,t)-orderings of digraphs. We do this by studying graphs which admit acyclic orientations that contain an out-branching and in-branching which are arc-disjoint (such an orientation is called good). A 2T-graph is a graph whose edge set can be decomposed into two edge-disjoint spanning trees. It is a well-known result due to Tutte and Nash-Williams, respectively, that every 4-edge-connected graph contains a spanning 2T-graph. Vertex-minimal 2T-graphs with at least two vertices which are known as generic circuits play an important role in rigidity theory for graphs. We prove that every generic circuit has a good orientation. Using this result we prove that if (Formula presented.) is 2T-graph whose vertex set has a partition (Formula presented.) so that each (Formula presented.) induces a generic circuit (Formula presented.) of (Formula presented.) and the set of edges between different (Formula presented.) 's form a matching in (Formula presented.), then (Formula presented.) has a good orientation. We also obtain a characterization for the case when the set of edges between different (Formula presented.) 's form a double tree, that is, if we contract each (Formula presented.) to one vertex, and delete parallel edges we obtain a tree. All our proofs are constructive and imply polynomial algorithms for finding the desired good orderings and the pairs of arc-disjoint branchings which certify that the orderings are good. We identify a structure which can be used to certify that a given 2T-graph does not have a good orientation.

Original languageEnglish
JournalJournal of Graph Theory
Volume96
Issue number4
Pages (from-to)594-618
ISSN0364-9024
DOIs
Publication statusPublished - Mar 2021

Keywords

  • 2T-graph
  • acyclic digraph
  • acyclic orientation
  • branchings
  • generic circuit
  • NP-complete problem
  • polynomial algorithm
  • rigidity matroid
  • spanning trees
  • vertex ordering

Fingerprint

Dive into the research topics of 'Good orientations of unions of edge-disjoint spanning trees'. Together they form a unique fingerprint.

Cite this