ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 30(2) (2010) 265-274
DOI: 10.7151/dmgt.1492


Mustapha Chellali

LAMDA-RO Laboratory, Department of Mathematics
University of Blida
B.P. 270, Blida, Algeria

Teresa W. Haynes

Department of Mathematics, East Tennessee State University
Johnson City, TN 37614 USA

Lutz Volkmann

Lehrstuhl II für Mathematik, RWTH Aachen University
Templergraben 55, D-52056 Aachen, Germany


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 βk(G). A graph G is called βk--stable if βk(G-e) = βk(G) for every edge e of E(G). First we give a necessary and sufficient condition for βk--stable graphs. Then we establish four equivalent conditions for βk--stable trees.

Keywords: k-independence stable graphs, k-independence.

2010 Mathematics Subject Classification: 05C69.


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

Received 6 December 2008
Revised 30 June 2009
Accepted 30 June 2009