A058862 Number of chordal labeled graphs (connected or not) with n nodes.

1, 2, 8, 61, 822, 18154, 617675, 30888596, 2192816760, 215488096587, 28791414081916, 5165908492061926, 1234777416771739141, 391374602835914994534, 164188178238479142509452

Offset: 1

Author

Robert Castelo, Jan 06 2001

Keywords

• nonn
• nice
• more

References

• N. C. Wormald, Counting labeled chordal graphs. Graphs Combin. 1 (1985), no. 2, 193-200.

Links

• Ursula Hebert-Johnson, Daniel Lokshtanov, and Eric Vigoda, Counting and Sampling Labeled Chordal Graphs in Polynomial Time, arXiv:2308.09703 [cs.DS], 2023.
• Jun Kawahara, Toshiki Saitoh, Hirofumi Suzuki, and Ryo Yoshinaka, Enumerating All Subgraphs without Forbidden Induced Subgraphs via Multivalued Decision Diagrams, arXiv:1804.03822 [cs.DS], 2018.

Crossrefs

Cf. A007134.

Programs

Mathematica

A007134 = Cases[Import["https://oeis.org/A007134/b007134.txt", "Table"],
   {, }][[All, 2]];
c[n_ /; 1 <= n <= Length[A007134]] := A007134[[n]];
a[n_] := a[n] = If[n == 0, 0, c[n] + 1/n * Sum[k*Binomial[n, k]*c[k]*
   a[n - k], {k, 1, n + 1}]];
Table[a[n], {n, 1, 15}] (* Jean-François Alcover, Jul 20 2022 *)

Formula

From the relation G(x)=exp(g(x)) between generating functions for connected g(x) and all G(x) labeled structures and considering generating functions for chordal graphs (c_n, A007134), we have a(n) = c(n) + 1/n * Sum_{k=1}^(n - 1) k * binomial(n, k) * c(k) * a(n - k). [Formula edited by Michael De Vlieger, Jul 04 2018]

Extensions

a(13) from formula by Falk Hüffner, Jul 24 2019

a(14)-a(15) from Brendan McKay, Jun 05 2021