Good orientations of 2T-graphs

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

Publication date 25 March 2019

Directed graphs (digraphs), tournaments (05C20)

Abstract: 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 orientation. Using this result we prove that if

G

is 2T-graph whose vertex set has a partition

V_{1}, V_{2}, l d o t s, V_{k}

so that each

V_{i}

induces a generic circuit

G_{i}

of

G

and the set of edges between different

G_{i}

's form a matching in

G

, then

G

has a good orientation. We also obtain a characterization for the case when the set of edges between different

G_{i}

's form a double tree, that is, if we contract each

G_{i}

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 also identify a structure which can be used to certify a 2T-graph which does not have a good orientation.

This page was built for publication: Good orientations of 2T-graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6316146)