7,1

We have unicyclic graphs of order n = m+4 with a cycle of length m. Only 4 nodes

of those graphs belong to the rooted trees attached to the cycle, so the orders

of those trees can be only 1,2,3,4, or 5. The set of graphs can be

divided in five subsets S_1, S_2, S_3, S_4, and S_5, such that

S_1 has trees of orders [5,1,1,...,1],

S_2 has trees of orders [4,2,1,...,1],

S_3 has trees of orders [3,3,1,...,1],

S_4 has trees of orders [3,2,2,1,...,1], and

S_5 has trees of orders [2,2,2,2,1,...,1].

|S_1| = 9 since there are 9 rooted trees with 5 points.

|S_2| = 4floor(m/2).

|S_3| = 3floor(m/2). We consider the 3 2-combinations (with repetition) of the 2

distinct rooted trees of order 3.

|S_4| = 2floor((m-1)^2/4) since floor((m-1)^2/4) is the number of bracelets with

m beads, 2 of which are red, 1 of which is blue.

With x=m-4, |S_5| = <(x^3 +9x^2 +(32-9(x mod 2))x)/48 +0.6>. The value of |S_5|

is equal to the number of m-bead bracelets with 4 red beads.

This sequence is the fifth column of table T of A058879.

Washington Bomfim, Table of n, a(n) for n = 7..100

Washington Bomfim, The 32 unicyclic graphs of order 9 with a penthagon..

With m = n-4, and x = m-4, a(n) = <(x^3 +9x^2 +(32-9(x mod 2))x)/48 +0.6> + 2floor((m-1)^2/4) + 7floor(m/2) + 9. Empirically for n odd a(n) = (n^3 +9n^2 -n +87)/48 Empirically for n even a(n) = (n^3 +9n^2 +8n +192-n%4*6)/48

E.g. a(9)=32. Click the link to see an illustration of the 32 unicyclic graphs of order 9 with a penthagon.

(PARI) m=n-4 x=m-4 a(n) = round((x^3+9*x^2+(32-9*(x%2))*x)/48+0.6)+2*floor((m-1)^2/4)+7*floor(m/2)+9

Cf. A058879, A005232, A000081, A002620.

Sequence in context: A138336 A094224 A128858 this_sequence A117101 A063840 A045000

Adjacent sequences: A141779 A141780 A141781 this_sequence A141783 A141784 A141785

nonn

Washington Bomfim (webonfim(AT)bol.com.br), Jul 31 2008