On total dominating sets in graphs

Abstract

A set $S$ of vertices in a graph $G(V,E)$ is called a dominating set if every vertex $v\in V$ is either an element of $S$ or is adjacent to an element of $S$. A set $S$ of vertices in a graph $G(V,E)$ is called a total dominating set if every vertex $v\in V$ is adjacent to an element of $S$. The domination number of a graph $G$ denoted by $\gamma (G)$ is the minimum cardinality of a dominating set in $G$. Respectively the total domination number of a graph $G$ denoted by ${\gamma }_t(G)$ is the minimum cardinality of a total dominating set in $G$. An upper bound for ${\gamma }_t(G)$ which has been achieved by Cockayne and et al. in $\cite{coc}$ is: for any graph $G$ with no isolated vertex and maximum degree $\Delta (G)$ and $n$ vertices, ${\gamma }_t(G)\le n-\Delta (G)+1$. Here we characterize bipartite graphs and trees which achieve this upper bound. Further we present some another upper and lower bounds for ${\gamma }_t(G)$. Also, for circular complete graphs, we determine the value of ${\gamma }_t(G)$.

5 pages