A058862 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

REFERENCES

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

LINKS

Table of n, a(n) for n=1..15.

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.

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]

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 *)

CROSSREFS

Cf. A007134.

Sequence in context: A188489 A085657 A005215 * A191482 A140722 A327078

Adjacent sequences: A058859 A058860 A058861 * A058863 A058864 A058865

KEYWORD