In 2004, T. Biedl et al. proposed an open problem in [2]: "What can be said about the size of maximum matchings in graphs with maximum degree k, for some fixed k≥4? Can we obtain a bound better than m/(2k-1)?" where m is the number of edges. In this paper, we derived a better lower bound, 2m/(3k-1), on the cardinality of maximum matchings in graphs with maximum degree k. For bipartite graphs, a tight lower bound is obtained.
展开▼
