Graphs with Large Disjunctive Total Domination Number

Abstract

Let $G$ be a graph with no isolated vertex. In this paper, we study a parameter that is a relaxation of arguably the most important domination parameter, namely the total domination number, ${\gamma }_t(G)$. A set $S$ of vertices in $G$ is a disjunctive total dominating set of $G$ if every vertex is adjacent to a vertex of $S$ or has at least two vertices in $S$ at distance $2$ from it. The disjunctive total domination number, ${\gamma }_t^d(G)$, is the minimum cardinality of such a set. We observe that ${\gamma }_t^d(G)\le {\gamma }_t(G)$. Let $G$ be a connected graph on $n$ vertices with minimum degree $\delta$. It is known [J. Graph Theory 35 (2000), 21--45] that if $\delta \ge 2$ and $n\ge 11$, then ${\gamma }_t(G)\le 4n/7$. Further [J. Graph Theory 46 (2004), 207--210] if $\delta \ge 3$, then ${\gamma }_t(G)\le n/2$. We prove that if $\delta \ge 2$ and $n\ge 8$, then ${\gamma }_t^d(G)\le n/2$ and we characterize the extremal graphs.

50 pages