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

Adriana Hansberg; Lutz Volkmann

Discussiones Mathematicae Graph Theory (2007)

  • Volume: 27, Issue: 1, page 93-103
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Adriana Hansberg, and Lutz Volkmann. "Characterization of block graphs with equal 2-domination number and domination number plus one." Discussiones Mathematicae Graph Theory 27.1 (2007): 93-103. <http://eudml.org/doc/270741>.

@article{AdrianaHansberg2007,
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. },
author = {Adriana Hansberg, Lutz Volkmann},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {domination; 2-domination; multiple domination; block graph; block graph},
language = {eng},
number = {1},
pages = {93-103},
title = {Characterization of block graphs with equal 2-domination number and domination number plus one},
url = {http://eudml.org/doc/270741},
volume = {27},
year = {2007},
}

TY - JOUR
AU - Adriana Hansberg
AU - Lutz Volkmann
TI - Characterization of block graphs with equal 2-domination number and domination number plus one
JO - Discussiones Mathematicae Graph Theory
PY - 2007
VL - 27
IS - 1
SP - 93
EP - 103
AB - 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.
LA - eng
KW - domination; 2-domination; multiple domination; block graph; block graph
UR - http://eudml.org/doc/270741
ER -

References

top
  1. [1] M. Blidia, M. Chellali and L. Volkmann, Bounds of the 2-domination number of graphs, Utilitas Math. 71 (2006) 209-216. Zbl1113.05072
  2. [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. [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. [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. Zbl0602.05043
  5. [5] T. Gallai, Über extreme Punkt-und Kantenmengen, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 2 (1959) 133-138. 
  6. [6] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). Zbl0890.05002
  7. [7] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater (eds.), Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998). Zbl0883.00011
  8. [8] C. Payan and N.H. Xuong, Domination-balanced graphs, J. Graph Theory 6 (1982) 23-32, doi: 10.1002/jgt.3190060104. Zbl0489.05049
  9. [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. Zbl0955.05088
  10. [10] J. Topp and L. Volkmann, On domination and independence numbers of graphs, Results Math. 17 (1990) 333-341. Zbl0748.05066
  11. [11] L. Volkmann, Foundations of Graph Theory (Springer, Wien, New York, 1996) (in German). Zbl0844.05001
  12. [12] L. Volkmann, Some remarks on lower bounds on the p-domination number in trees, J. Combin. Math. Combin. Comput., to appear. Zbl1137.05055
  13. [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. Zbl0954.05037

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.