Total domination versus paired domination

Schaudt, Oliver (2011) Total domination versus paired domination.
Technical Report , 10 p.

Abstract

A dominating set of a graph G is a vertex subset that any vertex of G either belongs to or is adjacent to. A total dominating set is a dominating set whose induced subgraph does not contain isolated vertices. The minimal size of a total dominating set, the total domination number, is denoted by gamma_t . The maximal size of an inclusionwise minimal total dominating set, the upper total domination number, is denoted by Gamma_t . A paired dominating set is a dominating set whose induced subgraph has a perfect matching. The minimal size of a paired dominating set, the paired domination number, is denoted by gamma_p . The maximal size of an inclusionwise minimal paired dominating set, the upper paired domination number, is denoted by Gamma_p . In this paper we prove several results on the ratio of these four parameters: For each r ge 2 we prove the sharp bound gamma_p/gamma_t le 2 - 2/r for K_{1,r} -free graphs. As a consequence, we obtain the sharp bound gamma_p/gamma_t le 2 - 2/(Delta+1) , where Delta is the maximum degree. We also show for each r ge 2 that {C_5,T_r} -free graphs fulfill the sharp bound gamma_p/gamma_t le 2 - 2/r , where T_r is obtained from K_{1,r} by subdividing each edge exactly once. We show that all of these bounds also hold for the ratio Gamma_p / Gamma_t . Further, we prove that a graph hereditarily has an induced paired dominating set iff gamma_p le Gamma_t holds for any induced subgraph. We also give a finite forbidden subgraph characterization for this condition. We exactly determine the maximal value of the ratio gamma_p / Gamma_t taken over the induced subgraphs of a graph. As a consequence, we prove for each r ge 3 the sharp bound gamma_p/Gamma_t le 2 - 2/r for graphs that do not contain the corona of K_{1,r} as subgraph. In particular, we obtain the sharp bound gamma_p/Gamma_t le 2 - 2/Delta .


Actions:
Download: [img] Postscript
Download (628Kb) | Preview
Download: [img] PDF
Download (135Kb) | Preview
Export as:
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2011-613
Depositing User: Oliver Schaudt
Date Deposited: 12 Apr 2011 00:00
Last Modified: 19 Dec 2011 09:44
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/613