## 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, γ_{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, γ_{t}^{d}(G), is the minimum cardinality of such a set. We observe that γ_{t}^{d}(G) ≤ γ_{t}(G). Let G be a connected graph on n vertices with minimum degree δ. It is known [J. Graph Theory 35 (2000), 21-45] that if δ ≥ 2 and n ≥ 11, then γ_{t}(G) ≤ 4n/7. Further [J. Graph Theory 46 (2004), 207-210] if δ ≥ 3, then γ_{t}(G) ≤ n/2. We prove that if δ ≥ 2 and n ≥ 8, then γ_{t}^{d}(G) ≤ n/2 and we characterize the extremal graphs.

Original language | English |
---|---|

Pages (from-to) | 255-282 |

Number of pages | 28 |

Journal | Discrete Mathematics and Theoretical Computer Science |

Volume | 17 |

Issue number | 1 |

Publication status | Published - 2015 |

## Keywords

- Disjunctive total dominating set
- Total dominating set

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science
- Discrete Mathematics and Combinatorics