Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650297 | Discrete Mathematics | 2007 | 8 Pages |
Let G=(V,E)G=(V,E) be a graph. A set S⊆VS⊆V is a restrained dominating set (RDS) if every vertex not in S is adjacent to a vertex in S and to a vertex in V⧹SV⧹S. The restrained domination number of G , denoted by γr(G)γr(G), is the minimum cardinality of an RDS of G . A set S⊆VS⊆V is a total dominating set (TDS) if every vertex in V is adjacent to a vertex in S. The total domination number of a graph G without isolated vertices, denoted by γt(G)γt(G), is the minimum cardinality of a TDS of G.Let δδ and ΔΔ denote the minimum and maximum degrees, respectively, in G. If G is a graph of order n with δ⩾2δ⩾2, then it is shown that γr(G)⩽n-Δγr(G)⩽n-Δ, and we characterize the connected graphs with δ⩾2δ⩾2 achieving this bound that have no 3-cycle as well as those connected graphs with δ⩾2δ⩾2 that have neither a 3-cycle nor a 5-cycle. Cockayne et al. [Total domination in graphs, Networks 10 (1980) 211–219] showed that if G is a connected graph of order n⩾3n⩾3 and Δ⩽n-2Δ⩽n-2, then γt(G)⩽n-Δγt(G)⩽n-Δ. We further characterize the connected graphs G of order n⩾3n⩾3 with Δ⩽n-2Δ⩽n-2 that have no 3-cycle and achieve γt(G)=n-Δγt(G)=n-Δ.