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

[BIBTex] [PDF] [PS]

k-INDEPENDENCE STABLE GRAPHS UPON EDGE REMOVAL

Mustapha Chellali

LAMDA-RO Laboratory, Department of Mathematics
University of Blida
B.P. 270, Blida, Algeria
e-mail: m_chellali@yahoo.com

Teresa W. Haynes

Department of Mathematics, East Tennessee State University
Johnson City, TN 37614 USA
e-mail: haynes@etsu.edu

Lutz Volkmann

Lehrstuhl II für Mathematik, RWTH Aachen University
Templergraben 55, D-52056 Aachen, Germany
e-mail: volkm@math2.rwth-aachen.de

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

References

[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