Total domination versus paired domination - Kölner UniversitätsPublikationsServer

Schaudt, Oliver (2011). Total domination versus paired domination. Working Paper. Open Access

Preview

PDF
zaik2011-613.pdf
Download (138kB) | Preview

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 .

Item Type:

Preprints, Working Papers or Reports (Working Paper)

Creators: