|
|||||
|
|
On equality in an upper bound for the restrained and total domination numbers of a graph |
|
| Authors: | Peter Dankelmann Johannes H Hattingh Lisa R Markus |
| Institution: | a School of Mathematical and Statistical Sciences, University of KwaZulu-Natal, Durban 4041, South Africa b Department of Mathematics, Durban Institute of Technology, Durban 4000, South Africa c Department of Mathematics and Statistics, Georgia State University, Atlanta, GA 30303, USA d School of Mathematics, Statistics, and Information Technology, University of KwaZulu-Natal, Pietermaritzburg 3209, South Africa e Department of Mathematics, De Anza College, Cupertino, CA 95014, USA |
| Abstract: | Let G=(V,E) be a graph. A set S⊆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?S. The restrained domination number of G, denoted by γr(G), is the minimum cardinality of an RDS of G. A set S⊆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), 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, then it is shown that γr(G)?n-Δ, and we characterize the connected graphs with δ?2 achieving this bound that have no 3-cycle as well as those connected graphs with δ?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?3 and Δ?n-2, then γt(G)?n-Δ. We further characterize the connected graphs G of order n?3 with Δ?n-2 that have no 3-cycle and achieve γt(G)=n-Δ. |
| Keywords: | 05C69 |
| 本文献已被 ScienceDirect 等数据库收录！ | |