# 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

## Access Full Article

top## Abstract

top## How to cite

topAdriana 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] M. Blidia, M. Chellali and L. Volkmann, Bounds of the 2-domination number of graphs, Utilitas Math. 71 (2006) 209-216. Zbl1113.05072
- [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. Zbl0602.05043
- [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). Zbl0890.05002
- [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] C. Payan and N.H. Xuong, Domination-balanced graphs, J. Graph Theory 6 (1982) 23-32, doi: 10.1002/jgt.3190060104. Zbl0489.05049
- [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] J. Topp and L. Volkmann, On domination and independence numbers of graphs, Results Math. 17 (1990) 333-341. Zbl0748.05066
- [11] L. Volkmann, Foundations of Graph Theory (Springer, Wien, New York, 1996) (in German). Zbl0844.05001
- [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] 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 ?

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