Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Good orientations of 2T-graphs   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,\ldots{},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.

13
The categories of this paper are: quant-ph
10
The categories of this paper are: q-bio
16
The categories of this paper are: stat
9
The categories of this paper are: nlin
26
The categories of this paper are: bayes-an
33
The categories of this paper are: plasm-ph
29
The categories of this paper are: funct-an
30
The categories of this paper are: q-alg
6
The categories of this paper are: astro-ph
15
The categories of this paper are: nucl-ex
11
The categories of this paper are: hep-lat
3
The categories of this paper are: physics
23
The categories of this paper are: solv-int
1
The categories of this paper are: cs
36
The categories of this paper are: cmp-lg
34
The categories of this paper are: chem-ph