A New Upper Bound on Total Domination Number of Bipartite Graphs

Abstract

Let $G$ be a graph. A subset $S\subseteq V(G)$ is called a total dominating set if every vertex of $G$ is adjacent to at least one vertex of $S$. The total domination number, ${\gamma }_t$($G$), is the minimum cardinality of a total dominating set of $G$. In this paper using a greedy algorithm we provide an upper bound for ${\gamma }_t$($G$), whenever $G$ is a bipartite graph and $\delta (G)$ $\ge$ $k$. More precisely, we show that if $k$ > 1 is a natural number, then for every bipartite graph $G$ of order $n$ and $\delta (G)\ge k$, ${\gamma }_t$($G$) $\le$ $n(1-\frac{k!}{{\prod }_{i=0}^{k-1}(\frac{k}{k-1}+i)}).$

10 pages, journal