# Good orientations of 2T-graphs

@article{BangJensen2019GoodOO, title={Good orientations of 2T-graphs}, author={J. Bang-Jensen and S. Bessy and J. Huang and M. Kriesell}, journal={arXiv: Combinatorics}, year={2019} }

In this paper we study graphs which admit acyclic orientations that contain a pair of arc-disjoint out-branching and in-branching (such an orientation is called good) and we focus on edge-minimal such graphs. A 2T-graph is a graph whose edge set can be decomposed into two edge-disjoint spanning trees. 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… Expand

#### References

SHOWING 1-10 OF 25 REFERENCES

Good acyclic orientations of 4-regular 4-connected graphs.

- Mathematics
- 2019

We study graphs which admit an acyclic orientation that contains an out-branching and in-branching which are arc-disjoint (such an orientation is called {\bf good}). A {\bf 2T-graph} is a graph whose… Expand

Small degree out-branchings

- Mathematics, Computer Science
- J. Graph Theory
- 2003

It is proved that any degree requirement in out-branchings of acyclic digraphs can be polynomially checked. Expand

Digraphs with the path-merging property

- Mathematics, Computer Science
- J. Graph Theory
- 1995

In this paper we study those digraphs D for which every pair of internally disjoint (X, Y)-paths P1, P2 can be merged into one (X, Y)-path P* such that V(P1) ∪ V(P2), for every choice of vertices X,… Expand

Decomposing k-ARc-Strong Tournaments Into Strong Spanning Subdigraphs

- Mathematics, Computer Science
- Comb.
- 2004

This paper conjecture that every k-arc-strong tournament contains k arc-disjoint spanning strong subdigraphs is formed, which solves a conjecture of Bang-Jensen and Gutin. Expand

Arc-disjoint spanning sub(di)graphs in digraphs

- Mathematics, Computer Science
- Theor. Comput. Sci.
- 2012

We prove that a number of natural problems concerning the existence of arc-disjoint directed and ''undirected'' (spanning) subdigraphs in a digraph are NP-complete. Among these are the following of… Expand

A proof of Connelly's conjecture on 3-connected circuits of the rigidity matroid

- Computer Science, Mathematics
- J. Comb. Theory, Ser. B
- 2003

It is proved that every 3-connected generic circuit can be obtained from K4 by a sequence of extensions by obtaining a special case of a conjecture of Hendrickson on generically globally rigid graphs. Expand

Arc-disjoint paths and trees in 2-regular digraphs

- Computer Science, Mathematics
- Discret. Appl. Math.
- 2013

It is proved that the first problem remains NP-complete for 2-regular digraphs, whereas the second problem turns out to be polynomial when the authors do not prescribe the root in advance. Expand

Edge-disjoint in- and out-branchings in tournaments and related path problems

- Computer Science, Mathematics
- J. Comb. Theory, Ser. B
- 1991

Good characterizations in Edmonds' sense are given for the following problems for tournaments and a proof is given by C. Thomassen that problem (1) is NP-complete for digraphs in general. Expand

On a Closure Concept in Claw-Free Graphs

- Computer Science
- J. Comb. Theory, Ser. B
- 1997

A suucient condition for hamiltonicity in claw-free graphs, the equivalence of some conjectures on ham Miltonicity in 2-tough graphs and the Hamiltonicity of 7-connected claw- free graphs are obtained as corollaries. Expand

On a Closure Concept in Claw-Free Graphs

- Mathematics
- 1997

IfGis a claw-free graph, then there is a graphcl(G) such that (i)Gis a spanning subgraph ofcl(G), (ii)cl(G) is a line graph of a triangle-free graph, and (iii)the length of a longest cycle inGand… Expand