彩8彩票|官网登录

當前位置: 彩8彩票|官网登录 / 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   投稿信箱:mathweb@sdu.edu.cn

Copyright@山東大學數學學院

微信公眾號
<acronym id="igsm0"></acronym>
<rt id="igsm0"></rt>
<tr id="igsm0"><code id="igsm0"></code></tr>
<rt id="igsm0"><xmp id="igsm0"><rt id="igsm0"></rt>
<option id="igsm0"><xmp id="igsm0">
<tr id="igsm0"><xmp id="igsm0">
<tr id="igsm0"><optgroup id="igsm0"></optgroup></tr><tr id="igsm0"><optgroup id="igsm0"></optgroup></tr>
<rt id="igsm0"></rt>
<option id="igsm0"><xmp id="igsm0">
<tr id="igsm0"><xmp id="igsm0">
<tr id="igsm0"><xmp id="igsm0">
彩8彩票|官网登录 澳发彩票|手机app下载 四川快乐12开奖结果 天王彩票|官网登录 广东36选7走势图 重庆快乐十分开奖结果 云南快乐十分开奖结果 山西21选5开奖结果 华东15选5走势图 河北福彩排列5开奖结果 青海快3基本走势图 河南福彩20选5开奖走势图 炫乐彩票|手机app下载 豪彩vip|手机app下载 baijiale|官网登录 河北福彩排列5开奖结果