Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: k-independent

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Maximal k-independent sets in graphs

100%

Blidia M., Chellali M., Favaron O., Meddah N.

Discussiones Mathematicae Graph Theory

2008

tom 28

nr 1

151-163

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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Blidia M.

1 Chellali M.

1 Favaron O.

1 Meddah N.

1 2008

Wyniki wyszukiwania

Maximal k-independent sets in graphs