Integer k-matchings of graphs: k-Berge–Tutte formula, k-factor-critical graphs and k-barriers

Abstract An integer k -matching of a graph G is a function h that assigns to each edge an integer in { 0 , … , k } such that ∑ e ∈ Γ ( v ) h ( e ) ≤ k for each vertex v , where Γ ( v ) is the set of edges incident with v . The integer k -matching number of G is the maximum number of ∑ e ∈ E ( G ) h ( e ) over all integer k -matchings h of G . When k is even, Yan Liu and Xiaohui Liu proved that the integer k -matching number of G equals k times its fractional matching number. In this paper, when k is odd, we prove the integer k -matching analogue of the Berge-Tutte Formula, define k -factor-critical graph, k -barrier and k -extreme, respectively, give two sufficient and necessary conditions of k -factor-critical graph which is similar to those of factor-critical graph, and obtain some properties about k -barrier and k -extreme, respectively.