Abstract
For any graph G, let α′(G) and α′min(G) be the maximum cardinality and minimum cardinality among all maximal matchings in G, respectively, and let γ′(G) and γt ′(G) be the edge domination number and edge total domination number of G, respectively. In this paper, we first show some properties of maximal matchings and further determine the exact values of α′(G) and α′min(G) for a complete multipartite graph G. Then, we disclose relationships between maximal matchings and minimal edge dominating sets, and thus obtain the exact values of γ′(G) and γt′(G) for a complete multipartite graph G.
Acknowledgements
The authors are grateful to the referees for their valuable suggestions which result in the present version of the paper.
Research was partially supported by Fundamental Research Funds for the Central Universities (2012WLB), the Foundation for distinguished Young Teachers, Shanghai Education Committee (No. sdl10023), and the Key Programs of Wuxi City College of Vocational Technology (WXCY-2012-GZ-007).