Dense arbitrarily partitionable graphs
Discussiones Mathematicae Graph Theory2015Vol. 36(1), pp. 5–5
Citations Over TimeTop 20% of 2015 papers
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 G > n-4 2 + 12 edges is AP or belongs to few classes of exceptional graphs.
Related Papers
- → A kind of conditional vertex connectivity of star graphs(2008)111 cited
- → Algebraic connectivity for vertex-deleted subgraphs, and a notion of vertex centrality(2009)12 cited
- → Augmenting a(k—1)-Vertex-ConnectedMultigraph to an ℓ-Edge-Connected and k-Vertex-Connected Multigraph(1999)5 cited
- → A connected subgraph maintaining high connectivity(2013)1 cited
- → High connectivity keeping connected subgraph(2011)