Labelled Graphs with Small Vertex Degrees and P -Recursiveness
I. P. Goulden, David M. Jackson · SIAM Journal on Algebraic and Discrete Methods · 1986
We show that the number of labelled graphs with vertices of degrees 1, 2, 3 or 4 only satisfy linear recurrence equations, and are therefore P-recursive. We conjecture that the number of labelled graphs with vertices whose degrees belong to a given finite set is also P-recursive.