科研之友
微信
新浪微博
Facebook
分享链接
摘要
The perfect matching polytope of a graph G is the convex hull of the incidence vectors of all perfect matchings in G. A graph is called perfect matching compact (shortly, PM-compact), if its perfect matching polytope has diameter one. This paper gives a complete characterization of simple PM-compact Hamiltonian bipartite graphs. We first define two families of graphs, called the H2C-bipartite graphs and the H23-bipartite graphs, respectively. Then we show that, for a simple Hamiltonian bipartite graph G with vertical bar V(G)vertical bar >= 6, G is PM-compact if and only if G is K-3,K-3, or G is a spanning Hamiltonian subgraph of either an H2C-bipartite graph or an H23-bipartite graph.
- 出版日期2015
- 单位郑州大学
