Mathematics – Combinatorics
Scientific paper
2008-10-26
Mathematics
Combinatorics
5 pages
Scientific paper
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)\leq 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)$.
Atapour Maryam
Soltankhah Nasrin
No associations
LandOfFree
On total dominating sets in graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On total dominating sets in graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On total dominating sets in graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-594931