A constructive characterization of trees with equal total domination and disjunctive domination numbers

  • Michael A. Henning
  • Sinclair A. Marcon
Keywords: Domination, disjunctive domination, trees

Abstract

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to a vertex in S. The total domination number, yt(G), of G is the minimum cardinality of a total dominating set of G. A set S of vertices in G is a disjunctive dominating set in G if every vertex not in S is adjacent to a vertex of S or has at least two vertices in S at distance 2 from it in G. The disjunctive domination number, yd2 (G), of G is the minimum cardinality of a disjunctive dominating set in G. By denition, we have yd2 (T) ≤ yt(T). In this paper, we provide a constructive characterization of the trees T achieving equality in this bound.

Keywords: Domination, disjunctive domination, trees

Published
2016-09-08
Section
Articles

Journal Identifiers


eISSN: 1727-933X
print ISSN: 1607-3606