Paper Info
Title
Total domination versus paired domination.
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 >= 2 we prove the sharp bound gamma(p) /gamma(t) <= 2-2/r for K-1,K-r-free graphs. As a consequence, we obtain the sharp bound gamma(p) /gamma(t) <= 2-2/(Delta + 1), where Delta is the maximum degree. We also show for each r >= 2 that {C-5, T-r}free graphs fulfill the sharp bound gamma(p)/gamma(t) <= 2-2/r, where T-r is obtained from K-1,K-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 if and only if gamma(p) <= 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 >= 3 the sharp bound gamma(p)/Gamma(t) <= 2 -2/r for graphs that do not contain the corona of K-1,K-r as subgraph. In particular, we obtain the sharp bound gamma(p)/Gamma(t) <= 2 -2/Delta
Year
DOI
Venue
2012
10.7151/dmgt.1614
DISCUSSIONES MATHEMATICAE GRAPH THEORY
Keywords
Field
DocType
total domination,upper total domination,paired domination,upper paired domination,generalized claw-free graphs
Graph,Discrete mathematics,Dominating set,Combinatorics,Vertex (geometry),Induced subgraph,Matching (graph theory),Domination analysis,Mathematics
Journal
Volume
Issue
ISSN
32
3
1234-3099
Citations 
PageRank 
References 
2
0.40
13
Authors
1
Name
Order
Citations
PageRank
Oliver Schaudt19521.74