0,5

A connected graph is called k-decomposable if it is possible to remove some edges and leave a graph with at least two connected components in which every component has at least k nodes.

Every connected graph with < 2k nodes is automatically k-indecomposable.

Necessary conditions are that a 4-indecomposable tree may not contain a path with >= 8 nodes, nor two node-disjoint paths with >= 4 nodes each.

Comment from Brendan McKay, Feb 15 2007: A necessary and sufficient condition seems to be that there are no two node-disjoint subtrees each of which is P_4 or K_{1,3}.

Comment from Brendan McKay, Feb 15 2007: Alternatively, a tree with n vertices is k-decomposable iff, for each edge, removing that edge leaves a component with at most k-1 vertices. Finding the maximal k such that a tree is k-decomposable is easy to do in linear time.

The counts of 1-indecomposable (1,0,0,0,...), 2-indecomposable (1,1,1,1,1,1,...) or 3-indecomposable (1,1,1,2,3,3,4,4,5,5,6,6,7,7,...) trees with number of nodes = 1,2,3,4,... are all trivial.

G.f.: f(x) / ((1-x)*(1-x^2)*(1-x^3)^2) where f(x) = 1 - x^2 - 2*x^3 + x^4 + 3*x^5 + 3*x^6 + 2*x^7 - 4*x^8 - 5*x^9 - 3*x^10 + 3*x^11 + 4*x^12 + x^13 - x^14 - x^15.

Rather than show some 4-indecomposable trees, instead we show all four 3-indecomposable trees with 7 nodes:

O-O-O-O-O....O..........O.O...O...O

....|........|..........|/.....\./.

....O....O-O-O-O-O..O-O-O-O...O-O-O

....|........|..........|....../.\.

....O........O..........O.....O...O

On the other hand, O-O-O-O-O-O-O is 3-decomposable, because removing the third edge gives O-O-O O-O-O-O, with 2 connected components each with >= 3 nodes.

Cf. A000055, A125709.

Sequence in context: A105614 A116441 A116051 this_sequence A125882 A057758 A057125

Adjacent sequences: A124590 A124591 A124592 this_sequence A124594 A124595 A124596

nonn

David Applegate (david(AT)research.att.com) and N. J. A. Sloane (njas(AT)research.att.com), Feb 14 2007, extended with generating function Feb 25 2007