3
$\begingroup$

How many cycle-free connected graphs are there on n vertices, none of which has degree >m?

e.g for m=1 there is 1 graph for n=1,2, 0 otherwise. For m=2 there is always 1 graph.

I am particularly interested in the m=4 case, as I was originally trying to count isomers of straight-chain alkanes.

  • 0
    It is in OEIS: you missed a $2$ before the $3$.2012-01-14

2 Answers 2

3

OEIS sequence A000602 seems to be exactly what you want: ‘Number of n-node unrooted quartic trees; number of n-carbon alkanes C(n)H(2n+2) ignoring stereoisomers’, with extensive references. There’s a table of the values for $n=0$ through $n=60$ here. This sequence is discussed in this paper by Rains & Sloane and in P. Flajolet and R. Sedgewick, Analytic Combinatorics, p. 478; the book is pretty heavy going, but it’s available for free download here. There does not appear to be any nice formula.

The $n=3$ case is OEIS A000672, which also appears to have no nice formula.

-1

I see that If $B(z)$ is the OGF of alkanes (EIS A000602), which are unrooted trees, then $B(z) = 1 + z + z^2 + z^3 + 2 z^4 + 3 z^5 + 5 z^6 + 9 z^7 + 18 z^8 + 35 z^9 + \ldots$

But what is the lower or upper bound on the coefficient of $z^n$? It would be really helpful if you could tell something about it.

  • 1
    It appears to me that this answer provides the OEIS info that was already provided by Brian M. Scott, and pretty much nothing else. If you have a question, you can ask that in a comment. It is not fit for an answer. And, this answer was 3.5 months later.2012-10-20