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
Access Full Article
top
Abstract
topHow to cite
topMostafa 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] 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] 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] 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] 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). Zbl0890.05002
NotesEmbed ?
topYou 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.