Maximal matching and edge domination in complete multipartite graphs

摘要

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.