Let k be a positive integer and G = (V(G),E(G)) a graph. A subset S of V(G) is a k-independent set of G if the subgraph induced by the vertices of S has maximum degree at most k-1. The maximum cardinality of a k-independent set of G is the k-independence number βₖ(G). A graph G is called β¯ₖ-stable if βₖ(G-e) = βₖ(G) for every edge e of E(G). First we give a necessary and sufficient condition for β¯ₖ-stable graphs. Then we establish four equivalent conditions for β¯ₖ-stable trees.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1492,
author = {Mustapha Chellali and Teresa W. Haynes and Lutz Volkmann},
title = {k-independence stable graphs upon edge removal},
journal = {Discussiones Mathematicae Graph Theory},
volume = {30},
year = {2010},
pages = {265-274},
zbl = {1214.05103},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1492}
}
Mustapha Chellali; Teresa W. Haynes; Lutz Volkmann. k-independence stable graphs upon edge removal. Discussiones Mathematicae Graph Theory, Tome 30 (2010) pp. 265-274. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1492/
[000] [1] M. Blidia, M. Chellali and L. Volkmann, Some bounds on the p-domination number in trees, Discrete Math. 306 (2006) 2031-2037, doi: 10.1016/j.disc.2006.04.010. | Zbl 1100.05069
[001] [2] J.F. Fink and M.S. Jacobson, n-domination in graphs, in: Graph Theory with Applications to Algorithms and Computer (John Wiley and sons, New York, 1985) 283-300.
[002] [3] G. Gunther, B. Hartnell and D.F. Rall, Graphs whose vertex independence number is unaffected by single edge addition or deletion, Discrete Appl. Math. 46 (1993) 167-172, doi: 10.1016/0166-218X(93)90026-K. | Zbl 0792.05116