PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2008 | 28 | 1 | 151-163
Tytuł artykułu

Maximal k-independent sets in graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Słowa kluczowe
Wydawca
Rocznik
Tom
28
Numer
1
Strony
151-163
Opis fizyczny
Daty
wydano
2008
otrzymano
2007-01-18
poprawiono
2008-01-08
zaakceptowano
2008-01-08
Twórcy
  • LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria
  • LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria
  • Univ. Paris-Sud, LRI, URM 8623, Orsay, F-91405, France, CNRS, Orsay, F91405
  • LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria
Bibliografia
  • [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).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1398
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.