Bounds on maximum bb-matchings

In this note, we study bounds on the maximum cardinality of a bb-matching, where a bb-matching is an edge set Mb⊆EMb⊆E in a graph G=(V,E)G=(V,E) with the constraint that dMb(v)≤bdMb(v)≤b for every vertex vv. Here dMb(v)dMb(v) is the degree of vv in the subgraph induced by MbMb and b∈Nb∈N is a constant. If b=1b=1, then bb-matchings are ordinary matchings. For the maximum cardinality of an ordinary matching, we derive ν(G)≥2m3k−1 for k≥3k≥3, where ν(G)ν(G) denotes the maximum cardinality of a matching in GG, mm is the number of edges, and kk is the maximum degree of GG. This answers an open question proposed by Biedl, Demaine, Duncan, Fleischer and Kobourov [T. Biedl, E. Demaine, C. Duncan, R. Fleischer, S. Kobourov, Tight bounds on maximal and maximum matchings, Discrete Math. 285 (1–3) (2004) 7–15]. For the maximum cardinality of a bb-matching, we derive νb(G)νb−1(G)≤1+4b−23b2−5b+2 for b≥3b≥3, where νb(G)νb(G) denotes the maximum cardinality of a bb-matching in GG.