Michael A. Henning ; Viroshan Naicker - Graphs with large disjunctive total domination number

dmtcs:2104 - Discrete Mathematics & Theoretical Computer Science, April 22, 2015, Vol. 17 no. 1 - https://doi.org/10.46298/dmtcs.2104
Graphs with large disjunctive total domination numberArticle

Authors: Michael A. Henning 1; Viroshan Naicker 2

  • 1 Department of Pure and Applied Mathematics [Johannesburg]
  • 2 Department of Mathematics [Grahamstown]

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


Volume: Vol. 17 no. 1
Section: Graph Theory
Published on: April 22, 2015
Submitted on: November 4, 2014
Keywords: Total dominating set,Disjunctive total dominating set,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-HC] Computer Science [cs]/Human-Computer Interaction [cs.HC]

2 Documents citing this article

Consultation statistics

This page has been seen 359 times.
This article's PDF has been downloaded 581 times.