报告人：王秀梅

工作单位: 郑州大学

报告时间：6月8日10:00

地点：二楼南阶梯教室

报告摘要:

A geometric object of great interest in combinatorial optimization is the perfect match- ing polytope of a graph G —the convex hull of the incidence vectors of all perfect match- ings of G. In any investigation concerning the perfect matching polytope, one may assume that G is matching covered — that is, G is a connected graph (of order at least two) and each edge of G lies in some perfect matching.

A graph G is Birkhoff-von Neumann if its perfect matching polytope is characterized solely by non-negativity and degree constraints. A result of Balas (1981) implies that G is Birkhoff-von Neumann if and only if G does not contain a pair of vertex-disjoint odd cycles (C₁, C₂) such that G−V (C₁) −V (C₂) has a perfect matching. It follows immediately that the corresponding decision problem is in co-NP. However, it is not known to be in NP.

The combinatorial diameter of a polytope is the diameter of its 1-skeleton graph. A graph G is PM-compact if the combinatorial diameter of its perfect matching polytope equals one. A result of Chva´tal (1975) implies that G is PM-compact if and only if G does not contain a pair of vertex-disjoint even cycles (C₁, C₂) such that G − V (C₁) − V (C₂) has a perfect matching. Once again the corresponding decision problem is in co-NP, but it is not known to be in NP.

In this paper, we consider the intersection of the aforementioned problems. We give a complete characterization of matching covered graphs that are Birkhoff-von Neumann as well as PM-compact. (Thus the corresponding decision problem is in P.)

This is a joint work with Marcelo H. de Carvalho, Nishad Kothar, and Yixun Lin.

报告人简介：

王秀梅，郑州大学数学与统计学院教授、硕导，中国运筹学会图论组合分会理事，中国运筹学会数学优化分会理事，河南省运筹学会常务理事。1995年毕业于河南大学数学系获理学学士学位。2003年获得郑州大学运筹学与控制论方向硕士学位。2007年获郑州大学组合数学与最优化方向博士学位。随后留校工作至今。主要从事图论与组合优化的研究。主持自然科学基金项目2项，主持中国博士后科学基金面上资助项目1项。