On total domination and minimum maximal matchings in graphs

Abstract

A subset M of the edges of a graph G is a matching if no two edges in M are incident. A maximal matching is a matching that is not  contained in a larger matching. A subset S of vertices of a graph G with no isolated vertices is a total dominating set of G if every vertex of  G is adjacent to at least one vertex in S. Let µ ^∗ (G) and γt(G) be the minimum cardinalities of a maximal matching and a total dominating set in G, respectively. Let δ(G) denote the minimum degree in graph G. We observe that γt(G) ≤ 2µ ^∗ (G) when 1 ≤ δ(G) ≤ 2  and γt(G) ≤ 2µ ^∗ (G)−δ(G) + 2 when δ(G) ≥ 3. We show that the upper bound for the total domination number is tight for every fixed δ(G).  We provide a constructive characterization of graphs G satisfying γt(G) = 2µ ^∗ (G) and a polynomial time procedure to determine whether γt(G) = 2µ ^∗ (G) for a graph G with minimum degree two.