Maximal k-independent sets in graphs

Mostafa Blidia; Mustapha Chellali; Odile Favaron; Nacéra Meddah

Discussiones Mathematicae Graph Theory (2008)

  • Volume: 28, Issue: 1, page 151-163
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Mostafa Blidia, et al. "Maximal k-independent sets in graphs." Discussiones Mathematicae Graph Theory 28.1 (2008): 151-163. <http://eudml.org/doc/270197>.

@article{MostafaBlidia2008,
abstract = {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.},
author = {Mostafa Blidia, Mustapha Chellali, Odile Favaron, Nacéra Meddah},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {k-independent; cactus; -independent},
language = {eng},
number = {1},
pages = {151-163},
title = {Maximal k-independent sets in graphs},
url = {http://eudml.org/doc/270197},
volume = {28},
year = {2008},
}

TY - JOUR
AU - Mostafa Blidia
AU - Mustapha Chellali
AU - Odile Favaron
AU - Nacéra Meddah
TI - Maximal k-independent sets in graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2008
VL - 28
IS - 1
SP - 151
EP - 163
AB - 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.
LA - eng
KW - k-independent; cactus; -independent
UR - http://eudml.org/doc/270197
ER -

References

top
  1. [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. Zbl1123.05066
  2. [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. Zbl0958.05102
  3. [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. Zbl0583.05049
  4. [4] O. Favaron, k-domination and k-independence in graphs, Ars Combin. 25 C (1988) 159-167. 
  5. [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. [6] G. Chartrand and L. Lesniak, Graphs & Digraphs: Third Edition (Chapman & Hall, London, 1996). 
  7. [7] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). Zbl0890.05002

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.