Szczegóły publikacji
Opis bibliograficzny
A generalization of an independent set with application to $(K_{q}; k)$-stable graphs / Andrzej ŻAK // Discrete Applied Mathematics ; ISSN 0166-218X. — 2014 — vol. 162, s. 421–427. — Bibliogr. s. 427, Abstr.
Autor
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 86779 |
|---|---|
| Data dodania do BaDAP | 2015-01-08 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.dam.2013.08.036 |
| Rok publikacji | 2014 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Discrete Applied Mathematics |
Abstract
We introduce a natural generalization of an independent set of a graph and give a sharp lower bound on its size. The bound generalizes the widely known Caro and Wei result on the independence number of a graph. We use this result in the following problem. Given non-negative real numbers alpha, beta the cost c(G) of a graph G is defined by c(G) = alpha vertical bar V(G)vertical bar + beta vertical bar E(G)vertical bar. We estimate the minimum cost of a (K-q; k)-vertex stable graph, i.e. a graph which contains a clique K-q after removing any k of its vertices. (C) 2013 Elsevier B.V. All rights reserved.
