A048193 Number of chordal graphs (or triangulated graphs) on n vertices.

1, 2, 4, 10, 27, 94, 393, 2119, 14524, 126758, 1392387, 19109099, 326005775, 6905776799, 181945055235

Offset

1,2

Comments

Graphs having no induced cycles of any length > 3, so every cycle in the graph has a chord, or is "triangulated".

All such graphs are perfect.

Euler transform of A048192. - Eric M. Schmidt, Mar 25 2015

Conjectured partial sums of A079456. - Sean A. Irvine, Jun 25 2022

This conjecture is true, because each connected component of a complement of a chordal graph is an isolated vertex, except for at most one. Indeed, otherwise there would exist edges A-B and C-D in two different connected components of the complement, and then A-C-B-D-A is an induced 4-cycle in the original graph. - Andrei Zabolotskii, Jan 02 2026

Links

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

S. Hougardy, Home Page

S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 2529-2571.

Eric Weisstein's World of Mathematics, Chordal Graph

Formula

a(n) = A048192(n) + A287427(n).

Crossrefs

Cf. A048192 (connected chordal graphs).

Cf. A287427 (disconnected chordal graphs).

Cf. A048194.

Sequence in context: A268522 A123428 A005975 * A123411 A278418 A321946

Adjacent sequences: A048190 A048191 A048192 * A048194 A048195 A048196

Keyword

nonn,more,changed

Author

Gordon Royle

Extensions

Edited by N. J. A. Sloane, Jul 04 2008

a(12) added (using A048192) by Eric M. Schmidt, Mar 25 2015

a(13) and a(14) added (using A048192) by Falk Hüffner, Jan 15 2016

a(15) added (using A048192) by Jakub Jablonski, Sep 15 2020

Status

approved