A Characterization of PM-compact Hamiltonian Bipartite Graphs

作     者：Xiu-mei WANG Jin-jiang YUAN Yi-xun LIN 

作者机构：School of Mathematics and Statistics Zhengzhou University 

出 版 物：《Acta Mathematicae Applicatae Sinica》 (应用数学学报（英文版）)

年 卷 期：2015年第31卷第2期

页      面：313-324页

核心收录：

学科分类：0809[工学-电子科学与技术（可授工学、理学学位）] 07[理学] 070205[理学-凝聚态物理] 08[工学] 070104[理学-应用数学] 0701[理学-数学] 0702[理学-物理学] 

基　　金：Supported by the National Natural Science Foundation of China under Grant No.11101383 11271338 and 11201432 

主　　题：perfect matching polytope perfect-matching graph bipartite graph hamiltonian graph 

摘      要：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 ｜V（G）｜ ≥ 6, G is PM-compact if and only if G is K3,3, or G is a spanning Hamiltonian subgraph of either an H2C-bipartite graph or an H23-bipartite graph.