Szczegóły publikacji
Opis bibliograficzny
Dense on-line arbitrarily partitionable graphs / Rafał KALINOWSKI // Discrete Applied Mathematics ; ISSN 0166-218X. — 2017 — vol. 226, s. 71–77. — Bibliogr. s. 77, Abstr. — Publikacja dostępna online od: 2017-05-08
Autor
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 106662 |
|---|---|
| Data dodania do BaDAP | 2017-07-17 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.dam.2017.04.006 |
| Rok publikacji | 2017 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Discrete Applied Mathematics |
Abstract
A graph image of order image is called arbitrarily partitionable (AP, for short) if, for every sequence image of positive integers with image, there exists a partition image of the vertex set image such that image induces a connected subgraph of order image, for image. In this paper we consider the on-line version of this notion, defined in a natural way. We prove that if image is a connected graph such with the independence number at most image and the degree sum of any pair of non-adjacent vertices is at least image, then image is on-line arbitrarily partitionable except for two graphs of small orders. We also prove that if image is a connected graph of order image and size image, then image is on-line AP unless image is even and image is a spanning subgraph of a unique exceptional graph. These two results imply that dense AP graphs satisfying one of the above two assumptions are also on-line AP. This is in contrast to sparse graphs where only few AP graphs are also on-line AP.
