# k-independence stable graphs upon edge removal

Mustapha Chellali; Teresa W. Haynes; Lutz Volkmann

Discussiones Mathematicae Graph Theory (2010)

- Volume: 30, Issue: 2, page 265-274
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topMustapha Chellali, Teresa W. Haynes, and Lutz Volkmann. "k-independence stable graphs upon edge removal." Discussiones Mathematicae Graph Theory 30.2 (2010): 265-274. <http://eudml.org/doc/270891>.

@article{MustaphaChellali2010,

abstract = {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.},

author = {Mustapha Chellali, Teresa W. Haynes, Lutz Volkmann},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {k-independence stable graphs; k-independence; -independence stable graphs; -independence},

language = {eng},

number = {2},

pages = {265-274},

title = {k-independence stable graphs upon edge removal},

url = {http://eudml.org/doc/270891},

volume = {30},

year = {2010},

}

TY - JOUR

AU - Mustapha Chellali

AU - Teresa W. Haynes

AU - Lutz Volkmann

TI - k-independence stable graphs upon edge removal

JO - Discussiones Mathematicae Graph Theory

PY - 2010

VL - 30

IS - 2

SP - 265

EP - 274

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

LA - eng

KW - k-independence stable graphs; k-independence; -independence stable graphs; -independence

UR - http://eudml.org/doc/270891

ER -

## References

top- [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. Zbl1100.05069
- [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.
- [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. Zbl0792.05116