Number of unlabeled trees that cover a wheel graph on n nodes. -------------------------------------------------------------- Example for n=5 All trees that cover a wheel on 5 nodes are equivalent to one of the following: o o o | | \ / \ o--o--o o--o o o--o o | | / o o o A number of considerations are required to count each possibility exactly once. We will firstly look at the case of trees rooted at the centre of the wheel and then consider what adjusments are necessary to count unrooted trees. Firstly considering the case of unlabeled trees that are rooted at the centre of the wheel. The graph will consist of k sub-trees with k in {1..n-1} attached to the centre and the remaining n-1-k nodes distributed over the k sub-trees. Each sub-tree consists of nothing more than a single node with up to two paths attached. For a sub-tree composed of t nodes there are ceilng(t/2) indistinguishable arrangements. For example, for t=5 the 3 possible sub-trees are: (with x denoting the node that attaches to the root) x--o--o--o--o o--x--o--o--o o--o--x--o--o | | | The total number of unlabeled trees rooted at the centre of the wheel is then given by the number of partitions of n-1 where there is one kind of 1's and 2's, two kinds of 3's and 4's, three kinds of 5's and 6's, etc. The terms for this sequence are A003293(n-1). A003293(n-1) = 1, 1, 2, 4, 7, 12, 21, 34, 56, 90, 143, 223 ... This sequence will count some unrooted trees more than once and so some adjustments are necessary to remove duplicates. Because only the central node has degree > 3, duplicates are only possible with trees with maximum degree 2 or 3. Case maximum degree 2: A tree with maximum degree 2 is just a path and for a fixed number of nodes this is unique. If we include only the rooted path that has an endpoint at the centre of the wheel then we need to exclude the ceiling(n/2)-1 paths that are rooted elsewhere. Case one node of maximum degree 3: This is a graph with a T shape. If we include only such trees where the vertex of degree is rooted at the wheel centre then we need to remove those that are not. For example, for n=6 the following T shape trees need to be excluded (with x denoting the centre of the wheel) o--o--o o--o--o--o o--o--o--o--o o--o--o--o--o | | | | x x x x | | o--o o A formula for the number to exclude is Sum_{k=3..n-1} ceiling(k/2)-1. Case two adjacent nodes of maximum degree 3: This is a graph with a H shape. For example, for n=8 there are the following rooted possibilities (with x denoting the centre of the wheel) o--o--o--o o--o--o--o--o o--o--o--o--o o--o--o o--o--o | | | | | o--x--o--o o--x--o o--x--o o--x--o--o--o o--o--x--o--o Of these it can be seen that the second and third are isomorphic to the final two. It is therefore necessary to exclude half the non symmetrical trees. The total number of such H trees is: Sum_{k=0..n-6} floor((k+2)/2) * floor((n-4-k)/2). For odd n the number of symmetric H trees is zero. For even n the number of symmetric H trees is floor((n-2)/4). Other cases with maximum degree 3: The only other possibility is to have two nodes of maximum degree at distance two from each other. These can only be rooted with the separating node at the centre of the wheel. We therefore do not need to exclude duplicates. Such a tree is illustrated below (with x denoting the centre of the wheel) o--o--o | x | o--o--o Final formula: Let a(n) be A002985(n) and b(n) be A003293(n). Let c(n) be 0 for odd n and floor((n-2)/4) for even n. Then a(n) = b(n-1) - (ceiling(n/2)-1) - (Sum_{k=3..n-1} ceiling(k/2)-1) - ((Sum_{k=0..n-6} floor((k+2)/2) * floor((n-4-k)/2)) - c(n)) / 2. This can be simplified to: a(n) = b(n-1) - A008804(n-3). where A008804(n) = (84 + 12*(-1)^n + 6*i*((-i)^n-i^n) + (85 + 3*(-1)^n)*n + 24*n^2 + 2*n^3)/96.