Geodesic
Maximal k-independent sets in graphs
Discussiones Mathematicae. Graph Theory, Tome 28 (2008) no. 1, pp. 151-163

Voir la notice de l'article provenant de la source Library of Science

A subset of vertices of a graph G is k-independent if it induces in G a subgraph of maximum degree less than k. The minimum and maximum cardinalities of a maximal k-independent set are respectively denoted iₖ(G) and βₖ(G). We give some relations between βₖ(G) and β_j(G) and between iₖ(G) and i_j(G) for j ≠ k. We study two families of extremal graphs for the inequality i₂(G) ≤ i(G) + β(G). Finally we give an upper bound on i₂(G) and a lower bound when G is a cactus.
Keywords: k-independent, cactus 
@article{DMGT_2008_28_1_a10,
     author = {Blidia, Mostafa and Chellali, Mustapha and Favaron, Odile and Meddah, Nac\'era},
     title = {Maximal k-independent sets in graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {151--163},
     publisher = {mathdoc},
     volume = {28},
     number = {1},
     year = {2008},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2008_28_1_a10/}
}
TY  - JOUR
AU  - Blidia, Mostafa
AU  - Chellali, Mustapha
AU  - Favaron, Odile
AU  - Meddah, Nacéra
TI  - Maximal k-independent sets in graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2008
SP  - 151
EP  - 163
VL  - 28
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2008_28_1_a10/
LA  - en
ID  - DMGT_2008_28_1_a10
ER  - 
%0 Journal Article
%A Blidia, Mostafa
%A Chellali, Mustapha
%A Favaron, Odile
%A Meddah, Nacéra
%T Maximal k-independent sets in graphs
%J Discussiones Mathematicae. Graph Theory
%D 2008
%P 151-163
%V 28
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2008_28_1_a10/
%G en
%F DMGT_2008_28_1_a10
Blidia, Mostafa; Chellali, Mustapha; Favaron, Odile; Meddah, Nacéra. Maximal k-independent sets in graphs. Discussiones Mathematicae. Graph Theory, Tome 28 (2008) no. 1, pp. 151-163. http://geodesic.mathdoc.fr/item/DMGT_2008_28_1_a10/