Upper total domination versus upper paired-domination

Abstract

Let G be a graph with no isolated vertices. A set S of vertices in G is a total dominating set of G if every vertex of G is adjacent to some vertex in S, while a paired-dominating set of G is a dominating set of vertices whose induced subgraph has a perfect matching. The maximum cardinality of a minimal total dominating set and a minimal paired-dominating set of G is the upper total domination number and upper paired-domination number of G, respectively, denoted by Γ _t (G) and Γ_pr(G). In this paper, we investigate the relationship between the upper total domination and upper paired-domination numbers of a graph. We show that for every graph G with no isolated vertex Γ _t (G) ≥ 1/2(Γ_pr(G) + 2), and we characterize the trees achieving this bound. For each positive integer k, we observe that there exist connected graphs G and H such that Γ_pr(G) – Γ _t (G) ≥ k and Γ _t (H) – Γ_pr(H) ≥ k.However for the family of trees Ton at least two vertices, we show that Γ _t (T) ≤ Γ _t (T).