k-independence stable graphs upon edge removal

• Autorzy: Mustapha Chellali , Teresa W. Haynes , Lutz Volkmann
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

k-independence stable graphs; k-independence

Kategorie tematyczne

• 05C69: Dominating sets, independent sets, cliques

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2010
• Tom: 30
• Numer: 2
• Strony: 265-274

Daty

wydano

2010

otrzymano

2008-12-06

poprawiono

2009-06-30

zaakceptowano

2009-06-30

Twórcy

autor

Mustapha Chellali

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

autor

Teresa W. Haynes

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

autor

Lutz Volkmann

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

Bibliografia

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

Identyfikatory

DOI

10.7151/dmgt.1492