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 ${\mu }^{\ast }(G)$ and ${\gamma }_t(G)$ be the minimum cardinalities of a maximal matching and a total dominating set in $G$, respectively. Let $\delta (G)$ denote the minimum degree in graph $G$. We observe that ${\gamma }_t(G)\le 2{\mu }^{\ast }(G)$ when $1\le \delta (G)\le 2$ and ${\gamma }_t(G)\le 2{\mu }^{\ast }(G)-\delta (G)+2$ when $\delta (G)\ge 3$. We show that the upper bound for the total domination number is tight for every fixed $\delta (G)$. We provide a constructive characterization of graphs $G$ satisfying ${\gamma }_t(G)=2{\mu }^{\ast }(G)$ and a polynomial time procedure to determine whether ${\gamma }_t(G)=2{\mu }^{\ast }(G)$ for a graph $G$ with minimum degree two.

10 pages, 2 figures