当前位置: 首页 / English / Academics / 正文

Good acyclic orientations of graphs

作者:   时间:2019-07-02   点击数:

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 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.

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


地址:中国山东省济南市山大南路27号   邮编:250100  

电话:0531-88364652  院长信箱:sxyuanzhang@sdu.edu.cn

Copyright@ m6体育入口(上海)贸易公司

微信公众号