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 .
Download: 
Postscript
Download (628Kb)  Preview 

Download: 
PDF
Download (135Kb)  Preview 
Export as:  
Editorial actions:  View Item (Login required) 
Item Type:  Paper (Technical Report) 

Citations:  2 (Google Scholar)  
Uncontrolled Keywords:  total domination upper total domination paired domination upper paired domination generalized clawfree graphs 
Subjects: 

Divisions:  Institute of Computer Science > Computer Science Department  Prof. Dr. Schrader Mathematical Institute > Prof. Dr. Faigle 
Related URLs: 
ZAIK Number:  zaik2011613 

Depositing User:  Oliver Schaudt 
Date Deposited:  12 Apr 2011 00:00 
Last Modified:  19 Dec 2011 09:44 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/613 