Total domination versus paired domination
Oliver Schaudt · Discussiones Mathematicae Graph Theory · 2012
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 γt.The maximal size of an inclusionwise minimal total dominating set, the upper total domination number, is denoted by Γ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 γp.The maximal size of an inclusionwise minimal paired dominating set, the upper paired domination number, is denoted by Γp.In this paper we prove several results on the ratio of these four parameters: For each r ≥ 2 we prove the sharp bound γp/γt ≤ 2 -2/r for K1,r-free graphs.As a consequence, we obtain the sharp bound γp/γt ≤ 2 -2/(∆ + 1), where ∆ is the maximum degree.We also show for each r ≥ 2 that {C5, Tr}-free graphs fulfill the sharp bound γp/γt ≤ 2 -2/r, where Tr is obtained from K1,r by subdividing each edge exactly once.We show that all of these bounds also hold for the ratio Γp/Γt.Further, we prove that a graph hereditarily has an induced paired dominating set iff γp ≤ Γ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 γp/Γt taken over the induced subgraphs of a graph.As a consequence, we prove for each r ≥ 3 the sharp bound γp/Γt ≤ 2 -2/r for graphs that do not contain the corona of K1,r as subgraph.In particular, we obtain the sharp bound γp/Γt ≤ 2 -2/∆.