new sequence that needs extending!

[Brendan McKay]

Agree on a(8)=13 (by hand).

Brendan.

* Brendan McKay <bdm at cs.anu.edu.au> [070216 16:40]:
> * 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