Szczegóły publikacji
Opis bibliograficzny
Small dense on-line arbitrarily partitionable graphs / Monika Bednarz, Agnieszka Burkot, Jakub KWAŚNY, Kamil Pawłowski, Angelika Ryngier // Applied Mathematics and Computation ; ISSN 0096-3003. — 2024 — vol. 470 art. no. 128582, s. 1-8. — Bibliogr. s. 8, Abstr. — Publikacja dostępna online od: 2024-02-02
Autorzy (5)
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 151815 |
|---|---|
| Data dodania do BaDAP | 2024-03-15 |
| Tekst źródłowy | URL |
| DOI | 10.1016/j.amc.2024.128582 |
| Rok publikacji | 2024 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Applied Mathematics and Computation |
Abstract
A graph is arbitrarily partitionable if for any sequence that satisfies it is possible to divide V into disjoint subsets such that and the subgraphs induced by all are connected. In this paper we inspect an on-line version of this concept and show that for graphs of order n, , and size greater than these two concepts are equivalent. Although our result concerns only finitely many graphs, together with a recent theorem of Kalinowski [5] it implies that arbitrarily partitionable graphs of any order n and size greater than are also on-line arbitrarily partitionable. For the proof of our main result, we show some lemmas providing sufficient conditions for a graph to be traceable or Hamiltonian-connected, and they are of interest on their own.
