DENSE ARBITRARILY PARTITIONABLE GRAPHS

作者：Kalinowski Rafal^*; Pilsniak Monika; Schiermeyer Ingo; Wozniak Mariusz

来源：Discussiones Mathematicae - Graph Theory, 2016, 36(1): 5-22.

DOI：10.7151/dmgt.1833

• arbitrarily partitionable graph
• Erdos-Gallai condition
• traceable graph
• 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 (V-1, ..., V-k) of the vertex set V(G) such that V-i induces a connected subgraph of order n(i) for i = 1, ..., k. In this paper we show that every connected graph G of order n >= 22 and with parallel to G parallel to > (
[GRAPHICS]
) + 12 edges is AP or belongs to few classes of exceptional graphs.

• 出版日期2016