Trees with equal 2-domination and 2-independence numbers
Mustapha Chellali; Nacéra Meddah
Discussiones Mathematicae Graph Theory (2012)
- Volume: 32, Issue: 2, page 263-270
- ISSN: 2083-5892
Access Full Article
top
Abstract
topHow to cite
topMustapha 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] M. Borowiecki, On a minimaximal kernel of trees, Discuss. Math. 1 (1975) 3-6. Zbl0418.05016
- [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] 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] 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] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs ( Marcel Dekker, New York, 1998). Zbl0890.05002
- [6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, New York 1998). Zbl0883.00011
NotesEmbed ?
topYou 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.