Szczegóły publikacji
Opis bibliograficzny
On the structure of arbitrarily partitionable graphs with given connectivity / Olivier Baudon, Florent Foucaud, Jakub PRZYBYŁO, Mariusz WOŹNIAK // Discrete Applied Mathematics ; ISSN 0166-218X. — 2014 — vol. 162, s. 381–385. — Bibliogr. s. 385, Abstr.
Autorzy (4)
- Baudon Olivier
- Foucaud Florent
- AGHPrzybyło Jakub
- AGHWoźniak Mariusz
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 79112 |
|---|---|
| Data dodania do BaDAP | 2014-01-22 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.dam.2013.09.007 |
| Rok publikacji | 2014 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Discrete Applied Mathematics |
Abstract
A graph G = (V, E) is arbitrarily partitionable if for any sequence tau of positive integers adding up to vertical bar V vertical bar, there is a sequence of vertex-disjoint subsets of V whose orders are given by tau, and which induce connected subgraphs. Such a graph models, e.g., a computer network which may be arbitrarily partitioned into connected subnetworks. In this paper we study the structure of such graphs and prove that unlike in some related problems, arbitrarily partitionable graphs may have arbitrarily many components after removing a cutset of a given size >= 2. The sizes of these components grow exponentially, though. (C) 2013 Elsevier B.V. All rights reserved.
