Geodesic
Dense Arbitrarily Partitionable Graphs
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 1, pp. 5-22

Voir la notice de l'article provenant de la source Library of Science

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 ‖G‖  gt; n-42 + 12 edges is AP or belongs to few classes of exceptional graphs.
Keywords: arbitrarily partitionable graph, Erdös-Gallai condition, traceable graph, perfect matching 
@article{DMGT_2016_36_1_a0,
     author = {Kalinowski, Rafa{\l} and Pil\'sniak, Monika and Schiermeyer, Ingo and Wo\'zniak, Mariusz},
     title = {Dense {Arbitrarily} {Partitionable} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {5--22},
     publisher = {mathdoc},
     volume = {36},
     number = {1},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a0/}
}
TY  - JOUR
AU  - Kalinowski, Rafał
AU  - Pilśniak, Monika
AU  - Schiermeyer, Ingo
AU  - Woźniak, Mariusz
TI  - Dense Arbitrarily Partitionable Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 5
EP  - 22
VL  - 36
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a0/
LA  - en
ID  - DMGT_2016_36_1_a0
ER  - 
%0 Journal Article
%A Kalinowski, Rafał
%A Pilśniak, Monika
%A Schiermeyer, Ingo
%A Woźniak, Mariusz
%T Dense Arbitrarily Partitionable Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 5-22
%V 36
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a0/
%G en
%F DMGT_2016_36_1_a0
Kalinowski, Rafał; Pilśniak, Monika; Schiermeyer, Ingo; Woźniak, Mariusz. Dense Arbitrarily Partitionable Graphs. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 1, pp. 5-22. http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a0/