ArticleOriginal scientific text

Title

Graphs with large double domination numbers

Authors 1

Affiliations

  1. School of Mathematics, Statistics, &, Information Technology, University of KwaZulu-Natal, Pietermaritzburg, 3209 South Africa

Abstract

In a graph G, a vertex dominates itself and its neighbors. A subset S ⊆ V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality of a double dominating set of G is the double domination number γ×2(G). If G ≠ C₅ is a connected graph of order n with minimum degree at least 2, then we show that γ×2(G)3n4 and we characterize those graphs achieving equality.

Keywords

bounds, domination, double domination, minimum degree two

Bibliography

  1. M. Blidia, M. Chellali, and T.W. Haynes, Characterizations of trees with equal paired and double domination numbers, submitted for publication.
  2. M. Blidia, M. Chellali, T.W. Haynes and M.A. Henning, Independent and double domination in trees, Utilitas Math., to appear.
  3. M. Chellali and T.W. Haynes, Paired and double domination in graphs, Utilitas Math., to appear.
  4. J. Harant and M.A Henning, On double domination in graphs, Discuss. Math. Graph Theory, to appear, doi: 10.7151/dmgt.1256.
  5. F. Harary and T.W. Haynes, Double domination in graphs, Ars Combin. 55 (2000) 201-213.
  6. T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).
  7. T.W. Haynes, S.T. Hedetniemi, and P.J. Slater (eds), Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998).
  8. C.S. Liao and G.J. Chang, Algorithmic aspects of k-tuple domination in graphs, Taiwanese J. Math. 6 (2002) 415-420.
  9. C.S. Liao and G.J. Chang, k-tuple domination in graphs, Information Processing Letters 87 (2003) 45-50, doi: 10.1016/S0020-0190(03)00233-3.
Pages:
13-28
Main language of publication
English
Received
2003-08-25
Accepted
2004-05-20
Published
2005
Exact and natural sciences