Maximal k-independent sets in graphs
Mostafa Blidia ; Mustapha Chellali ; Odile Favaron ; Nacéra Meddah
Discussiones Mathematicae Graph Theory, Tome 28 (2008), p. 151-163 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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 ij(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.

Publié le : 2008-01-01
EUDML-ID : urn:eudml:doc:270197 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1398,
     author = {Mostafa Blidia and Mustapha Chellali and Odile Favaron and Nac\'era Meddah},
     title = {Maximal k-independent sets in graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {28},
     year = {2008},
     pages = {151-163},
     zbl = {1169.05030},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1398}
}

Mostafa Blidia; Mustapha Chellali; Odile Favaron; Nacéra Meddah. Maximal k-independent sets in graphs. Discussiones Mathematicae Graph Theory, Tome 28 (2008) pp. 151-163. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1398/

[000] [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. | Zbl 1123.05066

[001] [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. | Zbl 0958.05102

[002] [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. | Zbl 0583.05049

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

[004] [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.

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

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