Dense on-line arbitrarily partitionable graphs

作者：Kalinowski Rafal^*

来源：Discrete Applied Mathematics, 2017, 226: 71-77.

DOI：10.1016/j.dam.2017.04.006

• Partitions of graphs
• Traceable graph
• Erdos-Gallai condition
• Ore condition
• Perfect matching

A graph G of order n is called arbitrarily partitionable (AP, for short) if, for every sequence (n(1), ... , n(k)) of positive integers with n(1)+ ... + n(k) = n, there exists a partition (Vi, ... , V-k) of the vertex set V(G) such that Vi induces a connected subgraph of order n(i) for i = 1, ... , k. In this paper we consider the on-line version of this notion, defined in a natural way.
We prove that if G is a connected graph such with the independence number at most [n/2] and the degree sum of any pair of non-adjacent vertices is at least n - 3, then G is online arbitrarily partitionable except for two graphs of small orders. We also prove that if G is a connected graph of order n and size parallel to GH parallel to > ((n-3)(2)) + 6, then G is on-line AP unless n is even and G 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.

• 出版日期2017-7-31