%0 Journal Article
%T Perfect 1-<i>k</i> Matchings of Bipartite Graphs
%A Wenduan Dai
%A Yan Liu
%A Yanfang Wu
%J Open Journal of Discrete Mathematics
%P 43-53
%@ 2161-7643
%D 2024
%I Scientific Research Publishing
%R 10.4236/ojdm.2024.144005
%X Let <i>k</i> be a positive integer and <i>G</i> a bipartite graph with bipartition <math display='inline' xmlns='http://www.w3.org/1998/Math/MathML'>
 <mrow>
  <mrow><mo>(</mo>
   <mrow>
    <mi>X</mi><mo>,</mo><mi>Y</mi></mrow>
  <mo>)</mo></mrow></mrow>
</math>

. A perfect 1-<i>k</i> matching is an edge subset <i>M</i> of <i>G</i> such that each vertex in <i>Y</i> is incident with exactly one edge in <i>M</i> and each vertex in <i>X</i> is incident with exactly <i>k</i> edges in <i>M</i>. A perfect 1-<i>k</i> matching is an optimal semi-matching related to the load-balancing problem, where a semi-matching is an edge subset <i>M</i> such that each vertex in <i>Y</i> is incident with exactly one edge in <i>M</i>, and a vertex in <i>X</i> can be incident with an arbitrary number of edges in <i>M</i>. In this paper, we give three sufficient and necessary conditions for the existence of perfect 1-<i>k</i> matchings and for the existence of 1-<i>k</i> matchings covering <math display='inline' xmlns='http://www.w3.org/1998/Math/MathML'>
 <mrow>
  <mrow><mo>|</mo> <mi>X</mi> <mo>|</mo></mrow><mo>&#x2212;</mo><mi>d</mi></mrow>
</math>

 vertices in <i>X</i>, respectively, and characterize <i>k</i>-elementary bipartite graph which is a graph such that the subgraph induced by all <i>k</i>-allowed edges is connected, where an edge is <i>k</i>-allowed if it is contained in a perfect 1-<i>k</i> matching.
%K Bipartite Graph
%K Semi-Matching
%K Perfect 1-<i>k</i> Matching
%K <i>k</i>-Elementary Graph
%U http://www.scirp.org/journal/PaperInformation.aspx?PaperID=136214