Szczegóły publikacji
Opis bibliograficzny
A note on arbitrarily vertex decomposable graphs / Antoni MARCZYK // Opuscula Mathematica ; ISSN 1232-9274. — Tytuł poprz.: Scientific Bulletins of Stanisław Staszic Academy of Mining and Metallurgy. Opuscula Mathematica. — 2006 — vol. 26 no. 1, s. 109–118. — Bibliogr. s. 117–118, Abstr.
Autor
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 31552 |
|---|---|
| Data dodania do BaDAP | 2007-02-17 |
| Tekst źródłowy | URL |
| Rok publikacji | 2006 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Opuscula Mathematica : rocznik Akademii Górniczo-Hutniczej im. Stanisława Staszica |
Abstract
A graph G of order n is said to be arbitrarily vertex decomposable if for each sequence (n1,..., nk) of positive integers such that n1 + ... + nk = n there exists a partition (V1,..., Vk) of the vertex set of G such that for each i ∈ {1,..., k}, Vi induces a connected subgraph of G on ni vertices. In this paper we show that if G is a two-connected graph on n vertices with the independence number at most ⌈n/2⌉ and such that the degree sum of any pair of non-adjacent vertices is at least n - 3, then G is arbitrarily vertex decomposable. We present another result for connected graphs satisfying a similar condition, where the bound n - 3 is replaced by n - 2.
