Back to Search
Start Over
Good orientations of unions of edge‐disjoint spanning trees
- 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.
- Subjects :
- acyclic orientation
0102 computer and information sciences
Disjoint sets
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Edge (geometry)
01 natural sciences
Polynomial algorithm
2T-graph
branchings
Combinatorics
vertex ordering
NP-complete problem
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
acyclic digraph
Discrete Mathematics and Combinatorics
0101 mathematics
ComputingMilieux_MISCELLANEOUS
Mathematics
Spanning tree
rigidity matroid
010102 general mathematics
polynomial algorithm
generic circuit
spanning trees
010201 computation theory & mathematics
Geometry and Topology
Acyclic orientation
NP-complete
MathematicsofComputing_DISCRETEMATHEMATICS
Subjects
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