Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2016 | 10.7151/dmgt.1833 | DISCUSSIONES MATHEMATICAE GRAPH THEORY |
Keywords | Field | DocType |
arbitrarily partitionable graph,Erdos-Gallai condition,traceable graph,perfect matching | Graph,Discrete mathematics,Combinatorics,Line graph,Matching (graph theory),Factor-critical graph,Mathematics,Perfect graph theorem | Journal |
Volume | Issue | ISSN |
36 | 1 | 1234-3099 |
Citations | PageRank | References |
2 | 0.38 | 5 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Rafał Kalinowski | 1 | 48 | 10.75 |
Monika Pilsniak | 2 | 29 | 5.42 |
Ingo Schiermeyer | 3 | 667 | 89.41 |
Mariusz Wozniak | 4 | 111 | 19.51 |