A characterization of PM-compact Hamiltonian bipartite graphs
A characterization of PM-compact Hamiltonian bipartite graphs
复制标题
DOI：
10.1007/s10255-015-0475-3
复制
发表时间：
2015-06
期刊：
影响因子：
--
通讯作者：
Xiumei Wang;Jinjiang Yuan;Yixun Lin
中科院分区：
文献类型：
--
作者：
Xiumei Wang;Jinjiang Yuan;Yixun Lin
The perfect matching polytope of a graphGis the convex hull of the incidence vectors of all perfect matchings inG. 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 graphGwith |V(G)| ≥ 6,Gis PM-compact if and only ifGisK3,3, orGis a spanning Hamiltonian subgraph of either an H2C-bipartite graph or an H23-bipartite graph.
