A048192 -id:A048192 - cp's OEIS frontend

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

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

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

Original entry on oeis.org

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

Offset: 1

Gordon F. Royle

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

S. Hougardy, Home Page
S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 2529-2571.
Eric Weisstein's World of Mathematics, Chordal Graph

Cf. A048192 (connected chordal graphs).
Cf. A287427 (disconnected chordal graphs).
Cf. A048194.

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

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

A241843 Number of simple connected graphs on n nodes that are non-chordal.

Original entry on oeis.org

0, 0, 0, 1, 6, 54, 581, 9503, 249169, 11607032, 1005452874, 164042264045, 50335602558672, 29003480904157108

Offset: 1

Travis Hoppe and Anna Petrone, Apr 29 2014

Travis Hoppe and Anna Petrone, Encyclopedia of Finite Graphs
Travis Hoppe and Anna Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644 [math.CO], 2014.
Eric Weisstein's World of Mathematics, Chordal Graph

Cf. A001349, A048192.
Cf. A287481 (not-necessarily connected simple non-chordal graphs).
Cf. A287482 (disconnected simple non-chordal graphs).

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

a(n) = A287481(n) - A287482(n). - Eric W. Weisstein, May 26 2017

a(13) and a(14) from formula by Falk Hüffner, Jan 15 2016

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

A243785 Number of unlabeled simple connected graphs with n nodes that are chordal but not integral.

Original entry on oeis.org

0, 0, 1, 4, 12, 56, 267, 1605, 11909, 109525

Offset: 1

Travis Hoppe and Anna Petrone, Jun 27 2014

Travis Hoppe and Anna Petrone, Encyclopedia of Finite Graphs.
Travis Hoppe and Anna Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644 [math.CO], 2014.
Eric Weisstein's World of Mathematics, Chordal Graph.
Eric Weisstein's World of Mathematics, Integral Graph.

Cf. A048192 (connected chordal graphs), A241842 (non-integral graphs).

Cf. A243786.

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

A243786 Number of unlabeled simple connected graphs with n nodes that are chordal and integral.

Original entry on oeis.org

1, 1, 1, 1, 3, 2, 5, 9, 2, 14

Offset: 1

Travis Hoppe and Anna Petrone, Jun 27 2014

Travis Hoppe and Anna Petrone, Encyclopedia of Finite Graphs.
Travis Hoppe and Anna Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644 [math.CO], 2014.
Eric Weisstein's World of Mathematics, Chordal Graph.
Eric Weisstein's World of Mathematics, Integral Graph.

Cf. A048192 (connected chordal graphs), A064731 (integral graphs).

Cf. A243785.

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

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

A243253 Number of graphs with n nodes that are chordal and Eulerian.

Original entry on oeis.org

1, 0, 1, 0, 3, 2, 13, 18, 116, 366, 2306, 13697

Offset: 1

Travis Hoppe and Anna Petrone, Jun 27 2014

Travis Hoppe and Anna Petrone, Encyclopedia of Finite Graphs
T. Hoppe and A. Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644, 2014
F. Hüffner, tinygraph, software for generating integer sequences based on graph properties, version 69d4186

Cf. A048192 (chordal graphs), A003049 (Eulerian graphs).

a(11) and a(12) added using tinygraph by Falk Hüffner, Jan 15 2016

A243787 Number of graphs with n nodes that are chordal and planar.

Original entry on oeis.org

1, 1, 2, 5, 14, 52, 228, 1209, 7463, 52520, 407856, 3414672, 30229061, 279124327

Offset: 1

Travis Hoppe and Anna Petrone, Jun 27 2014

Aharon Davidson, From Planck Area to Graph Theory: Topologically Distinct Black Hole Microstates, arXiv:1907.03090 [gr-qc], 2019.
Travis Hoppe and Anna Petrone, Encyclopedia of Finite Graphs
T. Hoppe and A. Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644 [math.CO], 2014.
F. Hüffner, tinygraph, software for generating integer sequences based on graph properties.

Cf. A048192 (chordal graphs), A003094 (planar graphs).

a(11)-a(14) added using tinygraph by Falk Hüffner, May 12 2019

A243788 Number of graphs with n nodes that are chordal and are K_4 free.

Original entry on oeis.org

1, 1, 2, 4, 11, 35, 124, 500, 2224, 10640, 53920, 285535, 1563849, 8798306

Offset: 1

Travis Hoppe and Anna Petrone, Jun 27 2014

K_4 is the complete graph on four vertices.

Travis Hoppe and Anna Petrone, Encyclopedia of Finite Graphs
T. Hoppe and A. Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644, 2014
F. Hüffner, tinygraph, software for generating integer sequences based on graph properties, version 69d4186

Cf. A048192 (chordal graphs), A079574 (K_4 free graphs).

a(11)-a(14) added using tinygraph by Falk Hüffner, Jan 15 2016

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A241843 Number of simple connected graphs on n nodes that are non-chordal.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A287427 Number of disconnected chordal simple graphs on n vertices.

Views

Author

Keywords

Links

Crossrefs

Formula

A243785 Number of unlabeled simple connected graphs with n nodes that are chordal but not integral.

Views

Author

Keywords

Links

Crossrefs

Formula

A243786 Number of unlabeled simple connected graphs with n nodes that are chordal and integral.

Views

Author

Keywords

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A243253 Number of graphs with n nodes that are chordal and Eulerian.

Views

Author

Keywords

Links

Crossrefs

Extensions

A243787 Number of graphs with n nodes that are chordal and planar.

Views

Author

Keywords

Links

Crossrefs

Extensions

A243788 Number of graphs with n nodes that are chordal and are K_4 free.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions