new sequence that needs extending!

[Brendan McKay]

* N. J. A. Sloane <njas at research.att.com> [070216 04:36]:
> 
> %I A124593
> %S A124593 1,1,1,2,3,6,11,13
> %N A124593 Number of 4-indecomposable trees with n nodes.
> %C A124593 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.
> %C A124593 Every connected graph with < 2k nodes is automatically k-indecomposable.
> %C A124593 A 4-indecomposable tree may not contain a path with >= 8 nodes, nor two node-disjoint paths with >= 4 nodes each.

I hope that isn't supposed to be precise characterisation.  The correct
rule seems to be that there are no two node-disjoint subtrees of which
each is P_4 or K_{1,3}. 

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 maximum k such that a tree is k-decomposable is easy to
do in linear time.  I wonder how fast it can be done for a general
graph.

Brendan.


> %C A124593 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 are all trivial.
> %e A124593 Rather than show some 4-indecomposable trees, instead we give all four 3-indecomposable trees with 7 nodes:
> %e A124593 O-O-O-O-O....O..........O.O...O...O
> %e A124593 ....|........|..........|/.....\./.
> %e A124593 ....O....O-O-O-O-O..O-O-O-O...O-O-O
> %e A124593 ....|........|..........|....../.\.
> %e A124593 ....O........O..........O.....O...O
> %e A124593 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.
> %Y A124593 Cf. A000055, A125709.
> %K A124593 nonn,more,new
> %O A124593 1,4
> %A A124593 David Applegate and njas, Feb 14 2007
> %E A124593 a(8) needs to be checked and the sequence extended. At present this entry is just a place-holder. It would also be good to get the analogous sequences for 5- and 6-indecomposable trees, as well as those in which the degree of every node is at most 4. The same questions can be asked about connected graphs rather than trees.
> 
> Some nice programming challenges!
> 
> Neil