Back to Search Start Over

Good orientations of unions of edge‐disjoint spanning trees

Authors :
Jing Huang
Matthias Kriesell
Stéphane Bessy
Jørgen Bang-Jensen
Department of Mathematics and Computer Science [Odense] (IMADA)
University of Southern Denmark (SDU)
Algorithmes, Graphes et Combinatoire (ALGCO)
Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM)
Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)
University of Victoria [Canada] (UVIC)
Institute of Mathematics - Technical University of Ilmenau
Ilmenau University of Technology [Germany] (TU)
ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019)
Source :
Bang-Jensen, J, Bessy, S, Huang, J & Kriesell, M 2021, ' Good orientations of unions of edge-disjoint spanning trees ', Journal of Graph Theory, vol. 96, no. 4, pp. 594-618 . https://doi.org/10.1002/jgt.22633, Journal of Graph Theory, Journal of Graph Theory, Wiley, 2021, 96 (4), pp.594-618. ⟨10.1002/jgt.22633⟩
Publication Year :
2020
Publisher :
Wiley, 2020.

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.

Details

ISSN :
10970118 and 03649024
Volume :
96
Database :
OpenAIRE
Journal :
Journal of Graph Theory
Accession number :
edsair.doi.dedup.....dda3669b2f4510a21c4038ab38f5f433
Full Text :
https://doi.org/10.1002/jgt.22633