报 告 人：卫兵（美国密西西比大学，教授）
报告时间：2023年12月26日（周二）下午3:30
报告地点：章辉楼442
联 系 人：晏卫根教授
欢迎老师与研究生参加！
报告摘要：In 1966, Gallai asked whether there is a vertex which passes through all longest paths of a connected graph. Although this has been verified for some special classes of graphs such as outerplanar graphs, circular arc graphs, and series-parallel graphs, the answer is negative for general graphs. In this talk, I will present among other results that if we replace the vertex by a bond, then the answer is affirmative. A {\it bond} of a graph is a minimal nonempty edge-cut. In particular, in any 2-connected graph, the set of all edges incident to a vertex is a bond, called a vertex-bond. Clearly, for a 2-connected graph, a path passes through a vertex $v$ if and only if it meets the vertex-bond with respect to $v$. Therefore, a very natural approach to Gallai's question is to study whether there is a bond meeting all longest paths. Let $p$ denote the length of a longest path of connected graphs. We show that there is a bond meeting all paths of length at least $p-1$ and $p-2$ for any 2 and 3-connected graph, respectively. For any $k$-connected graph $(k\ge3)$, we show that there is a bond meeting all paths of length at least $p-t+1$, where $t=\Big\lfloor\sqrt{\frac{k-2}{2}}\Big\rfloor$ if $p$ is even and $t=\Big\lceil\sqrt{\frac{k-2}{2}}\Big\rceil$ if $p$ is odd. Our results also provide analogs of the results on bonds meeting long cycles given in [P.-L. Wu, {\it Combin. Probab. Comput.}, 6 (1997), pp. 107--113; and S. McGuinness, {\it Combinatorica}, 25 (4) (2005), pp. 439--450].
本报告主要考虑k-连通图中Gallai问题的一个变体。报告人将介绍其在这方面取得的研究成果。
报告人简介：卫兵，现为美国密西西比大学数学系教授、研究生项目负责人，1992年博士毕业于德国柏林工业大学（Technical University of Berlin）。主要从事图的结构性理论、图的参数以及极图理论等方面的研究工作。在对图的圈，路和因子的结构，图的控制数，图的独立多项式等问题的研究中，获得一些深刻的结果。目前已发表科研论文九十余篇；若干国际SCI杂志的专业审稿人；应邀在国际或国内多个学术研究机构从事合作研究。在国内工作期间，曾获得博士后基金、多项国家自然科学基金、留学回国人员基金，香港裘槎基金等项目的资助等；曾经担任中国运筹学会副秘书长、中国图论学会秘书长；曾任中科院研究员、博士生导师。
