On total dominating sets in graphs
| dc.creator | Atapour, Maryam | |
| dc.creator | Soltankhah, Nasrin | |
| dc.date | 2008-10-26 | |
| dc.date.accessioned | 2026-07-07T10:13:18Z | |
| dc.date.available | 2026-07-07T10:13:18Z | |
| dc.description | 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 $γ(G)$ is the minimum cardinality of a dominating set in $G$. Respectively the total domination number of a graph $G$ denoted by $γ_t(G)$ is the minimum cardinality of a total dominating set in $G$. An upper bound for $γ_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 $Δ(G)$ and $n$ vertices, $γ_t(G)\leq n-Δ(G)+1$. Here we characterize bipartite graphs and trees which achieve this upper bound. Further we present some another upper and lower bounds for $γ_t(G)$. Also, for circular complete graphs, we determine the value of $γ_t(G)$. | |
| dc.description | 5 pages | |
| dc.identifier | https://arxiv.org/abs/0810.4667 | |
| dc.identifier | http://arxiv.org/abs/0810.4667 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/172484 | |
| dc.subject | Combinatorics | |
| dc.title | On total dominating sets in graphs | |
| dc.type | text |