- Tytuł:
- A note of arbitrarily vertex decomposable graphs
- Autorzy:
- Marczyk, A.
- Powiązania:
- https://bibliotekanauki.pl/articles/254919.pdf
- Data publikacji:
- 2006
- Wydawca:
- Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
- Tematy:
-
arbitrarily vertex decomposable graphs
traceable graphs
independence number
perfect matching - Opis:
- 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.
- Źródło:
-
Opuscula Mathematica; 2006, 26, 1; 109-118
1232-9274
2300-6919 - Pojawia się w:
- Opuscula Mathematica
- Dostawca treści:
- Biblioteka Nauki
Artykuł