DIKUL - logo
E-viri
Celotno besedilo
Recenzirano
  • Small dense on-line arbitra...
    Bednarz, Monika; Burkot, Agnieszka; Kwaśny, Jakub; Pawłowski, Kamil; Ryngier, Angelika

    Applied mathematics and computation, 06/2024, Letnik: 470
    Journal Article

    A graph G=(V,E) is arbitrarily partitionable if for any sequence (n1,…,nk) that satisfies n1+…+nk=|G| it is possible to divide V into disjoint subsets V=V1∪…∪Vk such that |Vi|=ni,i=1,…,k and the subgraphs induced by all Vi are connected. In this paper we inspect an on-line version of this concept and show that for graphs of order n, 8≤n≤14, and size greater than (n−32)+6 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 (n−32)+6 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.