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

Abstract

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

How to cite

top

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

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.