ArticleOriginal scientific text

Title

k-independence stable graphs upon edge removal

Authors 1, 2, 3

Affiliations

  1. LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria
  2. Department of Mathematics, East Tennessee State University, Johnson City, TN 37614 USA
  3. Lehrstuhl II für Mathematik, RWTH Aachen University, Templergraben 55, D-52056 Aachen, Germany

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.

Keywords

k-independence stable graphs, k-independence

Bibliography

  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.
Pages:
265-274
Main language of publication
English
Received
2008-12-06
Accepted
2009-06-30
Published
2010
Exact and natural sciences