Small dense on-line arbitrarily partitionable graphs.

A graph G = (V , E) is arbitrarily partitionable if for any sequence (n 1 , ... , n k) that satisfies n 1 + ... + n k = | G | it is possible to divide V into disjoint subsets V = V 1 ∪ ... ∪ V k such that | V i | = n i , i = 1 , ... , k and the subgraphs induced by all V i 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 − 3 2 ) + 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 − 3 2 ) + 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. [ABSTRACT FROM AUTHOR]