## 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 T on at least two vertices, we show that Gamma;_{t}(T) ≤ Γ_{pr}(T).

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

Pages (from-to) | 1-12 |

Number of pages | 12 |

Journal | Quaestiones Mathematicae |

Volume | 30 |

Issue number | 1 |

DOIs | |

Publication status | Published - Mar 2007 |

Externally published | Yes |

## Keywords

- Bounds
- Upper paired-domination
- Upper total domination

## ASJC Scopus subject areas

- Mathematics (miscellaneous)