Geodesic
Maximal k-independent sets in graphs
Discussiones Mathematicae. Graph Theory, Tome 28 (2008) no. 1, pp. 151-163 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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},
     year = {2008},
     volume = {28},
     number = {1},
     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
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
%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/

[1] M. Blidia, M. Chellali, O. Favaron and N. Meddah, On k-independence in graphs with emphasis on trees, Discrete Math. 307 (2007) 2209-2216, doi: 10.1016/j.disc.2006.11.007.

[2] M. Borowiecki and D. Michalak, Generalized independence and domination in graphs, Discrete Math. 191 (1998) 51-56, doi: 10.1016/S0012-365X(98)00092-2.

[3] O. Favaron, On a conjecture of Fink and Jacobson concerning k-domination and k-dependence, J. Combin. Theory (B) 39 (1985) 101-102, doi: 10.1016/0095-8956(85)90040-1.

[4] O. Favaron, k-domination and k-independence in graphs, Ars Combin. 25 C (1988) 159-167.

[5] J.F. Fink and M.S. Jacobson, n-domination, n-dependence and forbidden subgraphs, Graph Theory with Applications to Algorithms and Computer (John Wiley and sons, New York, 1985) 301-311.

[6] G. Chartrand and L. Lesniak, Graphs Digraphs: Third Edition (Chapman Hall, London, 1996).

[7] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).