Let k be a positive integer and G a bipartite graph with bipartition (X,Y). A perfect 1-k matching is an edge subset M of G such that each vertex in Y is incident with exactly one edge in M and each vertex in X is inc...Let k be a positive integer and G a bipartite graph with bipartition (X,Y). A perfect 1-k matching is an edge subset M of G such that each vertex in Y is incident with exactly one edge in M and each vertex in X is incident with exactly k edges in M. A perfect 1-k matching is an optimal semi-matching related to the load-balancing problem, where a semi-matching is an edge subset M such that each vertex in Y is incident with exactly one edge in M, and a vertex in X can be incident with an arbitrary number of edges in M. In this paper, we give three sufficient and necessary conditions for the existence of perfect 1-k matchings and for the existence of 1-k matchings covering | X |−dvertices in X, respectively, and characterize k-elementary bipartite graph which is a graph such that the subgraph induced by all k-allowed edges is connected, where an edge is k-allowed if it is contained in a perfect 1-k matching.展开更多
A graph G is close to regular or more precisely a （d, d ＋ k）-graph, if the degree of each vertex of G is between d and d ＋ k. Let d ≥ 2 be an integer, and let G be a connected bipartite （d, d＋k）-graph with par...A graph G is close to regular or more precisely a （d, d ＋ k）-graph, if the degree of each vertex of G is between d and d ＋ k. Let d ≥ 2 be an integer, and let G be a connected bipartite （d, d＋k）-graph with partite sets X and Y such that ｜X｜- ｜Y｜＋1. If G is of order n without an almost perfect matching, then we show in this paper that·n ≥ 6d ＋7 when k = 1,·n ≥ 4d＋ 5 when k = 2,·n ≥ 4d＋3 when k≥3.Examples will demonstrate that the given bounds on the order of G are the best possible.展开更多
Let B（G） denote the bipartite double cover of a non-bipartite graph G with v ≥ 2 vertices and s edges. We prove that G is a perfect 2-matching covered graph if and only if B（G） is a 1-extendable graph. Furthermor...Let B（G） denote the bipartite double cover of a non-bipartite graph G with v ≥ 2 vertices and s edges. We prove that G is a perfect 2-matching covered graph if and only if B（G） is a 1-extendable graph. Furthermore, we prove that B（G） is a minimally l-extendable graph if and only if G is a minimally perfect 2-matching covered graph and for each e = xy ∈ E（G）, there is an independent set S in G such that ｜ГG（S）｜ = ｜S｜ ＋ 1, x ∈ S and ｜ГG-xy（S）｜ = ｜S｜ Then, we construct a digraph D from B（G） or G and show that D is a strongly connected digraph if and only if G is a perfect 2-matching covered graph. So we design an algorithm in O（x√vε） time that determines whether G is a perfect 2-matching covered graph or not.展开更多
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.展开更多
文摘Let k be a positive integer and G a bipartite graph with bipartition (X,Y). A perfect 1-k matching is an edge subset M of G such that each vertex in Y is incident with exactly one edge in M and each vertex in X is incident with exactly k edges in M. A perfect 1-k matching is an optimal semi-matching related to the load-balancing problem, where a semi-matching is an edge subset M such that each vertex in Y is incident with exactly one edge in M, and a vertex in X can be incident with an arbitrary number of edges in M. In this paper, we give three sufficient and necessary conditions for the existence of perfect 1-k matchings and for the existence of 1-k matchings covering | X |−dvertices in X, respectively, and characterize k-elementary bipartite graph which is a graph such that the subgraph induced by all k-allowed edges is connected, where an edge is k-allowed if it is contained in a perfect 1-k matching.
文摘A graph G is close to regular or more precisely a （d, d ＋ k）-graph, if the degree of each vertex of G is between d and d ＋ k. Let d ≥ 2 be an integer, and let G be a connected bipartite （d, d＋k）-graph with partite sets X and Y such that ｜X｜- ｜Y｜＋1. If G is of order n without an almost perfect matching, then we show in this paper that·n ≥ 6d ＋7 when k = 1,·n ≥ 4d＋ 5 when k = 2,·n ≥ 4d＋3 when k≥3.Examples will demonstrate that the given bounds on the order of G are the best possible.
基金Acknowledgements The authors would like to thank the referees very much for their careful reading and their very instructive suggestions which improve this paper greatly. This work was supported in part by the National Natural Science Foundation of China （Grant No. 11201158）.
文摘Let B（G） denote the bipartite double cover of a non-bipartite graph G with v ≥ 2 vertices and s edges. We prove that G is a perfect 2-matching covered graph if and only if B（G） is a 1-extendable graph. Furthermore, we prove that B（G） is a minimally l-extendable graph if and only if G is a minimally perfect 2-matching covered graph and for each e = xy ∈ E（G）, there is an independent set S in G such that ｜ГG（S）｜ = ｜S｜ ＋ 1, x ∈ S and ｜ГG-xy（S）｜ = ｜S｜ Then, we construct a digraph D from B（G） or G and show that D is a strongly connected digraph if and only if G is a perfect 2-matching covered graph. So we design an algorithm in O（x√vε） time that determines whether G is a perfect 2-matching covered graph or not.
基金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.
