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

Author

Gordon F. Royle

Keywords

• nonn
• nice
• easy

Comments

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

Links

• 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

Crossrefs

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

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

Programs

Mathematica

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

Formula

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