Abstract:

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 V₁,…,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. This is joint work with Bang-Jensen, Bessy and Kriesell.

Speaker Introduction:

Huang Jing, University of Victoria

     Inviter:

Jin Yan，Professor of School of Mathematics

Date:

10:00  on July 3

Location:

Hall 924, Block B, Zhixin Building, Central Campus

Hosted by: School of Mathematics, Shandong University