A333865 Number of simple graphs on n nodes with vertex count > edge count + 1.

0, 1, 2, 4, 8, 18, 40, 100, 256, 705, 2057, 6370, 20803, 71725, 259678, 985244, 3905022, 16124936, 69188809, 307765510, 1416146859, 6727549181, 32938379216, 165942445714, 859020421012, 4563322971706, 24847598243116, 138533012486423, 790075521708603, 4605183081182354

Offset: 1

Author

Eric W. Weisstein, Apr 08 2020

Keywords

• nonn

Comments

These graphs correspond to "trivially ungraceful" graphs that do not have enough integers less than or equal to the edge count to cover all the vertices.

Links

• Eric Weisstein's World of Mathematics, Graceful Graph
• Eric Weisstein's World of Mathematics, Simple Graph
• Eric Weisstein's World of Mathematics, Ungraceful Graph

Crossrefs

Cf. A008406.

Cf. A308556 (number of simple ungraceful graphs on n nodes).

Programs

Mathematica

Get["Combinatorica`"] // Quiet;
Table[Total[Take[CoefficientList[GraphPolynomial[n, x], x], n - 1]], {n, 20}]

PARI

permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v, t) = {prod(i=2, #v, prod(j=1, i-1, my(g=gcd(v[i], v[j])); t(v[i]*v[j]/g)^g )) * prod(i=1, #v, my(c=v[i]); t(c)^((c-1)\2)*if(c%2, 1, t(c/2)))}
a(n)={my(s=0); if(n>1, forpart(p=n, s+=permcount(p)*polcoef(edges(p, i->1 + x^i + O(x^(n-1)))/(1-x), n-2) )); s/n!} \\ Andrew Howroyd, Apr 08 2020

Formula

a(n) <= A308556(n).

a(n) = Sum_{k=0..n-2} A008406(n, k). - Andrew Howroyd, Apr 08 2020

Extensions

Terms a(11) and beyond from Andrew Howroyd, Apr 08 2020