# 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 language English Journal of Graph Theory 96 4 594-618 0364-9024 https://doi.org/10.1002/jgt.22633 Published - 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.