Abstract
Let (Formula presented.) 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, (Formula presented.). A set (Formula presented.) of vertices in (Formula presented.) is a disjunctive total dominating set of (Formula presented.) if every vertex is adjacent to a vertex of (Formula presented.) or has at least two vertices in (Formula presented.) at distance (Formula presented.) from it. The disjunctive total domination number, (Formula presented.) , is the minimum cardinality of such a set. We observe that (Formula presented.). We prove that if (Formula presented.) is a connected graph of order (Formula presented.) , then (Formula presented.) and we characterize the extremal graphs. It is known that if (Formula presented.) is a connected claw-free graph of order (Formula presented.) , then (Formula presented.) and this upper bound is tight for arbitrarily large (Formula presented.). We show this upper bound can be improved significantly for the disjunctive total domination number. We show that if (Formula presented.) is a connected claw-free graph of order (Formula presented.) , then (Formula presented.) and we characterize the graphs achieving equality in this bound.
| Original language | English |
|---|---|
| Pages (from-to) | 1090-1110 |
| Number of pages | 21 |
| Journal | Journal of Combinatorial Optimization |
| Volume | 31 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - 1 Apr 2016 |
Keywords
- Claw-free
- Disjunctive total dominating set
- Total dominating set
ASJC Scopus subject areas
- Computer Science Applications
- Discrete Mathematics and Combinatorics
- Control and Optimization
- Computational Theory and Mathematics
- Applied Mathematics