A048193 -id:A048193 - cp's OEIS frontend

A048192 Number of connected chordal graphs on n vertices.

1, 1, 2, 5, 15, 58, 272, 1614, 11911, 109539, 1247691, 17566431, 305310547, 6558690953, 174688164414

Offset: 1

F. Hüffner, tinygraph, software for generating integer sequences based on graph properties, version 6e0a59d
Tim Kemp, An algorithmic approach to a conjecture of Chvátal on toughness and hamiltonicity of graphs, M. Sc. Thesis, University of Twente (Netherlands, 2020).
B. D. McKay, Chordal graphs
Eric Weisstein's World of Mathematics, Chordal Graph
Eric Weisstein's World of Mathematics, Connected Graph

Cf. A048193 (not-necessarily connected chordal graphs).
Cf. A287427 (disconnected chordal graphs).
Cf. A048194.

a(n) = A048193(n) - A287427(n). - Eric W. Weisstein, May 25 2017

Inverse Euler transform of A048193. - Andrew Howroyd, Nov 03 2017

a(12) added by Gordon F. Royle, Aug 05 2008
a(13) and a(14) added using tinygraph by Falk Hüffner, Jan 15 2016
a(15) added by Brendan McKay, Jan 07 2019

A048194 Total number of split graphs (chordal + chordal complement) on n vertices.

Original entry on oeis.org

1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, 5067146, 67997750, 1224275498, 29733449510, 976520265678, 43425320764422, 2616632636247976, 213796933371366930, 23704270652844196754, 3569464106212250952762, 730647291666881838671052

Offset: 1

Gordon F. Royle

Also number of bipartite graphs with n vertices and no isolated vertices in distinguished bipartite block, up to isomorphism; so a(n) equals first differences of A049312. - Vladeta Jovovic, Jun 17 2000
All split graphs are perfect. - Falk Hüffner, Nov 29 2015
Inverse Euler transform gives A007776 with initial 1. - Andrew Howroyd, Oct 03 2018

Alois P. Heinz, Table of n, a(n) for n = 1..40
B. A. Chat, S. Pirzada, and A. Iványi, Recognition of split-graphic sequences, Acta Universitatis Sapientiae, Informatica, 6, 2 (2014) 252-286.
Karen L. Collins and Ann N. Trenk, Finding Balance: Split Graphs and Related Classes, arXiv:1706.03092 [math.CO], June 2017.
Karen L. Collins and Ann N. Trenk, Finding Balance: Split Graphs and Related Classes, Electron. J. Combin., 25 (2018), #P1.73.
S. Hougardy, Home Page.
S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 2529-2571.
Vladeta Jovovic, Binary matrices up to row and column permutations.
Gordon F. Royle, Counting set covers and split graphs, J. Integer Seqs., Vol. 3 (2000), #00.2.6.
J. M. Troyka, Split graphs: combinatorial species and asymptotics, Electron. J. Combin., 26 (2019), #P2.42.
J. M. Troyka, Split graphs: combinatorial species and asymptotics, arXiv:1803.07248 [math.CO], 2019.
Eric Weisstein's World of Mathematics, Split Graph.
Index entries for sequences related to posets

Cf. A007776, A048192, A048193, A049312, A055080, A263859.

Detlef Pauly remarks that this is the unlabeled analog of A001831.

b[n_, i_] := b[n, i] = If[n == 0, {0}, If[i < 1, {}, Flatten @ Table[ Map[ Function[{p}, p + j*x^i], b[n - i*j, i - 1]], {j, 0, n/i}]]];
g[n_, k_] := g[n, k] = Sum[Sum[2^Sum[Sum[GCD[i, j]*Coefficient[s, x, i]* Coefficient[t, x, j], {j, 1, Exponent[t, x]}], {i, 1, Exponent[s, x]}]/ Product[i^Coefficient[s, x, i]*Coefficient[s, x, i]!, {i, 1, Exponent[s, x]}]/Product[i^Coefficient[t, x, i]*Coefficient[t, x, i]!, {i, 1, Exponent[t, x]}], {t, b[n + k, n + k]}], {s, b[n, n]}];
A[n_, k_] := g[Min[n, k], Abs[n - k]];
a[d_] := Sum[A[n, d - n], {n, 0, d}] - Sum[A[n, d - n - 1], {n, 0, d - 1}];
Table[a[n], {n, 1, 25}] (* Jean-François Alcover, May 26 2019, after Alois P. Heinz in A049312 *)

a(n) = A049312(n) - A049312(n-1) (see the Collins and Trenk link, Thms. 5 and 15). - Justin M. Troyka, Oct 29 2018
a(n) ~ A049312(n) ~ (1/n!) * Sum_{k=0..n} binomial(n,k) * 2^(k(n-k)) (see the Troyka link, Thms. 3.7 and 3.10). - Justin M. Troyka, Oct 29 2018
a(n) = A263859(n,1) + 1. - Geoffrey Critzer, Feb 05 2024

A287427 Number of disconnected chordal simple graphs on n vertices.

Original entry on oeis.org

0, 1, 2, 5, 12, 36, 121, 505, 2613, 17219, 144696, 1542668, 20695228, 347085846

Offset: 1

Eric W. Weisstein, May 24 2017

Eric Weisstein's World of Mathematics, Chordal Graph
Eric Weisstein's World of Mathematics, Disconnected Graph

Cf. A048193 (not-necessarily connected chordal graphs).

Cf. A048192 (connected chordal graphs).

a(n) = A048193(n) - A048192(n).

A287481 Number of (not-necessarily connected) non-chordal simple graphs on n vertices.

Original entry on oeis.org

0, 0, 0, 1, 7, 62, 651, 10227, 260144, 11878410, 1017605477, 165072063493, 50501705362177, 29054148751458689

Offset: 1

Eric W. Weisstein, May 25 2017

Eric Weisstein's World of Mathematics, Chordal Graph

Cf. A241843 (simple connected non-chordal graphs).

Cf. A287482 (simple disconnected non-chordal graphs).

a(n) = A241843(n) + A287482(n).

a(n) = A000088(n) - A048193(n).

a(11)-a(14) using formula by Falk Hüffner, Aug 10 2017

A342324 Largest number of maximal chordal node-induced subgraphs of an n-node graph.

Original entry on oeis.org

1, 1, 1, 4, 5, 12, 16, 36, 81

Offset: 1

Pontus von Brömssen, Mar 08 2021

This sequence is log-superadditive, i.e., a(m+n) >= a(m)*a(n). By Fekete's subadditive lemma, it follows that the limit of a(n)^(1/n) exists and equals the supremum of a(n)^(1/n). - Pontus von Brömssen, Mar 03 2022

			All graphs with at most three nodes are chordal, so a(n) = 1 for n <= 3 and any graph will be optimal (containing 1 maximal chordal subgraph).
For 4 <= n <= 9, the following graphs are optimal:
  n = 4: the 4-cycle;
  n = 5: the 5-cycle and the complete bipartite graph K_{2,3};
  n = 6: the 3-prism graph and the octahedral graph;
  n = 7: the 3-prism graph with one edge (not in a triangle) subdivided by an additional node, and the complete tripartite graph K_{2,2,3};
  n = 8: the gyrobifastigium graph;
  n = 9: the Paley graph of order 9.

Cf. A048192, A048193.

For a list of related sequences, see cross-references in A342211.

a(m+n) >= a(m)*a(n).

Lim a(n)^(1/n) >= 3^(4/9).

cp's OEIS Frontend

A048192 Number of connected chordal graphs on n vertices.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A048194 Total number of split graphs (chordal + chordal complement) on n vertices.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A287427 Number of disconnected chordal simple graphs on n vertices.

Views

Author

Keywords

Links

Crossrefs

Formula

A287481 Number of (not-necessarily connected) non-chordal simple graphs on n vertices.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A342324 Largest number of maximal chordal node-induced subgraphs of an n-node graph.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula