Maximal matching and edge domination in complete multipartite graphs
Wenyao Song, Lianying Miao, Haichao Wang, Yancai Zhao · International Journal of Computer Mathematics · 2013
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.