Graphs which contain k edge-disjoint spanning trees have been characterized by Tutte. Somewhat surprisingly, Thomassen proved that deciding whether a digraph contains a pair of arc-disjoint out-branching and in-branching is an NP-complete problem. This problem has since been studied for various classes of digraphs, giving rise to NP-completeness results as well as polynomial time solutions. 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). A 2T-graph is a graph whose edge set can be decomposed into two edge-disjoint spanning trees. We prove that every generic circuit has a good orientation. Using this result we show that if G is 2T-graph whose vertex set has a partition V1,…,Vk so that each Vi induces a generic circuit Gi of G and the set of edges between different Gi'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 Gi's form a double tree. This is joint work with Bang-Jensen, Bessy and Kriesell.
Huang Jing, University of Victoria
Jin Yan，Professor of School of Mathematics
10:00 on July 3
Hall 924, Block B, Zhixin Building, Central Campus
Hosted by: School of Mathematics, Shandong University