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...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.展开更多
With applications in communication networks,the minimum stretch spanning tree problem is to find a spanning tree T of a graph G such that the maximum distance in T between two adjacent vertices is minimized.The proble...With applications in communication networks,the minimum stretch spanning tree problem is to find a spanning tree T of a graph G such that the maximum distance in T between two adjacent vertices is minimized.The problem has been proved NP-hard and fixed-parameter polynomial algorithms have been obtained for some special families of graphs.In this paper,we concentrate on the optimality characterizations for typical classes of graphs.We determine the exact formulae for the complete k-partite graphs,split graphs,generalized convex graphs,and several planar grids,including rectangular grids,triangular grids,and triangulated-rectangular grids.展开更多
基金Supported by the National Natural Science Foundation of China under Grant No.11101383,11271338 and 11201432
文摘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.
基金by National Key R&D Program of China(No.2019YFB2101604).
文摘With applications in communication networks,the minimum stretch spanning tree problem is to find a spanning tree T of a graph G such that the maximum distance in T between two adjacent vertices is minimized.The problem has been proved NP-hard and fixed-parameter polynomial algorithms have been obtained for some special families of graphs.In this paper,we concentrate on the optimality characterizations for typical classes of graphs.We determine the exact formulae for the complete k-partite graphs,split graphs,generalized convex graphs,and several planar grids,including rectangular grids,triangular grids,and triangulated-rectangular grids.
