当前位置: 首页  学术动态

数学学科离散数学研究所学术报告(吴叶舟 浙江大学)

发布者:戴 情   发布时间:2021-07-03  浏览次数:65

报告题目Minimum T-Joins and Signed-Circuit Covering

 吴叶舟  浙江大学 教授

报告时间2021年7月5日10:00-11:00

报告地点:数计学院20幢308

 

摘要:Let $G$ be a graph and $T$ be a vertex subset of $G$ with even cardinality. A $T$-join of $G$ is a subset $J$ of edges such that a vertex of $G$ is incident with an odd number of edges in $J$ if and only if the vertex belongs to $T$. Minimum $T$-joins have many applications in combinatorial optimizations. In this paper, we show that a minimum $T$-join of a connected graph $G$ has at most $|E(G)|- 1/2 |E(\widehat{\, G\,})|$ edges where $\widehat{\,G\,}$ is the maximum bidegeless subgraph of $G$.  Further, we are able to use this result to show that every flow-admissible signed graph $(G,\sigma)$ has a signed-circuit cover with length at most $\min(8|E(G)|/3+|V(G)|/2,23|E(G)|/12+3|V(G)|/2)$. Particularly, every flow-admissible signed graph $(G,\sigma)$ with with minimum degree 3 has a signed-circuit cover with length at most $35|E(G)|/12}$. This is joint work with Dong Ye.

 

邀请人:朱绪鼎