A058862 -id:A058862 - cp's OEIS frontend

A007134 Number of connected labeled chordal graphs (or triangulated graphs) with n nodes.

1, 1, 4, 35, 541, 13302, 489287, 25864897, 1910753782, 193328835393, 26404671468121, 4818917841228328, 1167442027829857677, 374059462390709800421, 158311620026439080777076

Offset: 1

N. J. A. Sloane

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
N. C. Wormald, Counting labelled chordal graphs. Graphs Combin. 1 (1985), no. 2, 193-200.

Cf. A058862.

a(14)-a(15) from Brendan McKay, Jun 05 2021

A179534 Number of labeled split graphs on n vertices.

Original entry on oeis.org

1, 2, 8, 58, 632, 9654, 202484, 5843954, 233064944, 12916716526, 998745087980, 108135391731690, 16434082400952296, 3513344943520006118, 1058030578581541945316, 449389062270642095128546, 269419653009366144571801568, 228157953744571034350576205790

Offset: 1

Vladislav Bina, Jul 18 2010

A split graph is a graph whose vertices can be partitioned into a clique and an independent set. - Justin M. Troyka, Oct 28 2018

V. Bina, Enumeration of Labeled Split Graphs and Counts of Important Superclasses. In Adacher L., Flamini, M., Leo, G., Nicosia, G., Pacifici, A., Picialli, V. (Eds.). CTW 2011, Villa Mondragone, Frascati, pp. 72-75 (2011).

Andrew Howroyd, Table of n, a(n) for n = 1..100
E. A. Bender, L. B. Richmond, and N. C. Wormald, Almost all chordal graphs split, J. Austral. Math. Soc. (Series A), 38 (1985), 214-221.
V. Bina, Multidimensional probability distributions: Structure and learning, PHD Thesis. Fac. of Management, University of Economics in Prague (2011).
Venkatesan Guruswami, Enumerative aspects of certain subclasses of perfect graphs, Discrete Mathematics 205 (1999), 97-117.
J. M. Troyka, Split graphs: combinatorial species and asymptotics, arXiv:1803.07248 [math.CO], 2018-2019.
J. M. Troyka, Split graphs: combinatorial species and asymptotics, Electron. J. Combin., 26 (2019), #P2.42.

Cf. A047863, A048194, A058862, A006125.

A179534 := proc(n) local a,k; a := 1 ; for k from 2 to n do a := a+binomial(n,k)*( (2^k-1)^(n-k) -add(j*k*binomial(n-k,j)*(2^(k-1)-1)^(n-k-j)/(j+1), j=1..n-k) ) end do: a ; end proc: # R. J. Mathar, Jun 21 2011

a[n_] := 1 + Sum[Binomial[n,k]*((2^k-1)^(n-k) - Sum[j*k*Binomial[n-k,j]*(2^(k-1)-1)^(n-k-j)/(j+1), {j,1,n-k}]), {k,2, n}]; Array[a, 20] (* Stefano Spezia, Oct 29 2018 *)

b(n) = {sum(k=0, n, binomial(n, k)*2^(k*(n-k)))} \\ A047863(n)
a(n) = b(n) - n*b(n-1) \\ Andrew Howroyd, Jun 06 2021

a(n) = 1 + Sum_{k=2..n} binomial(n,k)*( (2^k-1)^(n-k) - Sum_{j=1..n-k} j*k*binomial(n-k,j)*(2^(k-1)-1)^(n-k-j) /(j+1) ).
From Justin M. Troyka, Oct 28 2018: (Start)
a(n) = [ Sum_{k=0..n} binomial(n,k) 2^(k(n-k)) ] - [ n Sum_{k=0..n-1} binomial(n-1,k)*2^(k(n-k-1)) ] (see the Troyka link, Cor. 3.4).
a(n) = A047863(n) - n*A047863(n-1) (see the Troyka link, Cor. 3.4).
a(n) ~ A047863(n) (see Bender, Richmond, and Wormald, Cor. 1). (End)

a(12)-a(16) corrected and terms a(17) and beyond from Andrew Howroyd, Jun 06 2021

A345024 a(n) is the number of maximal chains of labeled chordal graphs with n vertices.

Original entry on oeis.org

1, 1, 6, 576, 1416960, 120678543360, 455010170456862720, 95371866538619173904056320, 1383866987105877308750365304858542080, 1716187027583005555045945024371317843956845772800, 221917018834976627508152930913765491170568412125060985539788800, 3598055237740601485367382153175891099609454479883844294426214728495086488780800

Offset: 1

Brendan McKay, Jun 05 2021

a(n) is the number of sequences G[0], G[1], ..., G[n(n-1)/2] where each G[i] is a chordal graph with i edges and G[i] is a subgraph of G[i+1] for each i. All graphs are labeled.

Brendan McKay, Table of n, a(n) for n = 1..13

Cf. A058862.

A208356 Number of labeled star-like graphs on n vertices.

Original entry on oeis.org

1, 2, 8, 61, 762, 13204, 300155, 8950176

Offset: 1

Vladislav Bina, Feb 25 2012

nonn

Graph G is called star-like if and only if one of its clique trees forms a star.

The first seven terms published in the Bina Ph.D. thesis.

V. Bina, Multidimensional probability distributions: Structure and learning, Ph.D. Thesis. Fac. of Management, University of Economics in Prague (2011)

Cf. A179534, A006125, A058862 (sub- and superclasses)

cp's OEIS Frontend

A007134 Number of connected labeled chordal graphs (or triangulated graphs) with n nodes.

Views

Author

Keywords

References

Crossrefs

Extensions

A179534 Number of labeled split graphs on n vertices.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A345024 a(n) is the number of maximal chains of labeled chordal graphs with n vertices.

Views

Author

Keywords

Comments

Links

Crossrefs

A208356 Number of labeled star-like graphs on n vertices.

Views

Author

Keywords

Comments

Links

Crossrefs