ArticleOriginal scientific text

Title

Characterization of block graphs with equal 2-domination number and domination number plus one

Authors 1, 1

Affiliations

  1. Lehrstuhl II für Mathematik, RWTH Aachen University, 52056 Aachen, Germany

Abstract

Let G be a simple graph, and let p be a positive integer. A subset D ⊆ V(G) is a p-dominating set of the graph G, if every vertex v ∈ V(G)-D is adjacent with at least p vertices of D. The p-domination number γₚ(G) is the minimum cardinality among the p-dominating sets of G. Note that the 1-domination number γ₁(G) is the usual domination number γ(G). If G is a nontrivial connected block graph, then we show that γ₂(G) ≥ γ(G)+1, and we characterize all connected block graphs with γ₂(G) = γ(G)+1. Our results generalize those of Volkmann [12] for trees.

Keywords

domination, 2-domination, multiple domination, block graph

Bibliography

  1. M. Blidia, M. Chellali and L. Volkmann, Bounds of the 2-domination number of graphs, Utilitas Math. 71 (2006) 209-216.
  2. J.F. Fink and M.S. Jacobson, n-domination in graphs, in: Graph Theory with Applications to Algorithms and Computer Science (John Wiley and Sons, New York, 1985), 282-300.
  3. J.F. Fink and M.S. Jacobson, On n-domination, n-dependence and forbidden subgraphs, in: Graph Theory with Applications to Algorithms and Computer Science (John Wiley and Sons, New York, 1985), 301-311.
  4. J.F. Fink, M.S. Jacobson, L.F. Kinch and J. Roberts, On graphs having domination number half their order, Period. Math. Hungar. 16 (1985) 287-293, doi: 10.1007/BF01848079.
  5. T. Gallai, Über extreme Punkt-und Kantenmengen, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 2 (1959) 133-138.
  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. Payan and N.H. Xuong, Domination-balanced graphs, J. Graph Theory 6 (1982) 23-32, doi: 10.1002/jgt.3190060104.
  9. B. Randerath and L. Volkmann, Characterization of graphs with equal domination and covering number, Discrete Math. 191 (1998) 159-169, doi: 10.1016/S0012-365X(98)00103-4.
  10. J. Topp and L. Volkmann, On domination and independence numbers of graphs, Results Math. 17 (1990) 333-341.
  11. L. Volkmann, Foundations of Graph Theory (Springer, Wien, New York, 1996) (in German).
  12. L. Volkmann, Some remarks on lower bounds on the p-domination number in trees, J. Combin. Math. Combin. Comput., to appear.
  13. B. Xu, E.J. Cockayne, T.W. Haynes, S.T. Hedetniemi and S. Zhou, Extremal graphs for inequalities involving domination parameters, Discrete Math. 216 (2000) 1-10, doi: 10.1016/S0012-365X(99)00251-4.
Pages:
93-103
Main language of publication
English
Received
2005-12-07
Accepted
2006-10-18
Published
2007
Exact and natural sciences