# Trees with equal 2-domination and 2-independence numbers

• Volume: 32, Issue: 2, page 263-270
• ISSN: 2083-5892

top

## Abstract

top
Let G = (V,E) be a graph. A subset S of V is a 2-dominating set if every vertex of V-S is dominated at least 2 times, and S is a 2-independent set of G if every vertex of S has at most one neighbor in S. The minimum cardinality of a 2-dominating set a of G is the 2-domination number γ₂(G) and the maximum cardinality of a 2-independent set of G is the 2-independence number β₂(G). Fink and Jacobson proved that γ₂(G) ≤ β₂(G) for every graph G. In this paper we provide a constructive characterization of trees with equal 2-domination and 2-independence numbers.

## How to cite

top

Mustapha Chellali, and Nacéra Meddah. "Trees with equal 2-domination and 2-independence numbers." Discussiones Mathematicae Graph Theory 32.2 (2012): 263-270. <http://eudml.org/doc/271035>.

@article{MustaphaChellali2012,
abstract = {Let G = (V,E) be a graph. A subset S of V is a 2-dominating set if every vertex of V-S is dominated at least 2 times, and S is a 2-independent set of G if every vertex of S has at most one neighbor in S. The minimum cardinality of a 2-dominating set a of G is the 2-domination number γ₂(G) and the maximum cardinality of a 2-independent set of G is the 2-independence number β₂(G). Fink and Jacobson proved that γ₂(G) ≤ β₂(G) for every graph G. In this paper we provide a constructive characterization of trees with equal 2-domination and 2-independence numbers.},
author = {Mustapha Chellali, Nacéra Meddah},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {2-domination number; 2-independence number; trees},
language = {eng},
number = {2},
pages = {263-270},
title = {Trees with equal 2-domination and 2-independence numbers},
url = {http://eudml.org/doc/271035},
volume = {32},
year = {2012},
}

TY - JOUR
AU - Mustapha Chellali
AU - Nacéra Meddah
TI - Trees with equal 2-domination and 2-independence numbers
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 2
SP - 263
EP - 270
AB - Let G = (V,E) be a graph. A subset S of V is a 2-dominating set if every vertex of V-S is dominated at least 2 times, and S is a 2-independent set of G if every vertex of S has at most one neighbor in S. The minimum cardinality of a 2-dominating set a of G is the 2-domination number γ₂(G) and the maximum cardinality of a 2-independent set of G is the 2-independence number β₂(G). Fink and Jacobson proved that γ₂(G) ≤ β₂(G) for every graph G. In this paper we provide a constructive characterization of trees with equal 2-domination and 2-independence numbers.
LA - eng
KW - 2-domination number; 2-independence number; trees
UR - http://eudml.org/doc/271035
ER -

## References

top
1. [1] M. Borowiecki, On a minimaximal kernel of trees, Discuss. Math. 1 (1975) 3-6. Zbl0418.05016
2. [2] M. Chellali, O. Favaron, A. Hansberg and L. Volkmann, k-domination and k-independence in graphs: A Survey, Graphs and Combinatorics, 28 (2012) 1-55, doi: 10.1007/s00373-011-1040-3.
3. [3] O. Favaron, On a conjecture of Fink and Jacobson concerning k-domination and k-dependence, J. Combinat. Theory (B) 39 (1985) 101-102, doi: 10.1016/0095-8956(85)90040-1. Zbl0583.05049
4. [4] J.F. Fink and M.S. Jacobson, n-domination in graphs, in: Graph Theory with Applications to Algorithms and Computer Science., ed(s), Y. Alavi and A.J. Schwenk (Wiley, New York, 1985) 283-300.
5. [5] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs ( Marcel Dekker, New York, 1998). Zbl0890.05002
6. [6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, New York 1998). Zbl0883.00011

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