|
Search: id:A058863
|
|
|
| A058863 |
|
Number of connected labeled chordal graphs on n nodes with no induced path P_4; also the number of labeled trees with each vertex replaced by a clique. |
|
+0
5
|
|
| 1, 1, 4, 23, 181, 1812, 22037, 315569, 5201602, 97009833, 2019669961, 46432870222, 1168383075471, 31939474693297, 942565598033196, 29866348653695203, 1011335905644178273, 36446897413531401020
(list; graph; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
A subclass of chordal-comparability graphs.
|
|
REFERENCES
|
M. C. Golumbic (1978) Trivially perfect graphs, Discrete Mathematics, 24:105-107.
T. H. Ma and J. P. Spinrad (1991) Cycle-free partial orders and chordal comparability graphs, Order, 8:49-61.
E. S. Wolk (1965) A note on the comparability graph of a tree, Proc. Am. Math. Soc., 16:17-20.
|
|
LINKS
|
R. Castelo and N. C. Wormald, Enumeration of P4-free chordal graphs
R. Castelo and N. C. Wormald, Enumeration of P4-Free chordal graphs, Graphs and Combinatorics, 19:467-474, 2003.
|
|
FORMULA
|
c_n = 1 + Sum_{k=1}^{n-2} {n choose k} ( t_{n-k} - c_{n-k} ) where c_n is the number of connected graphs of this type and t_n is the total number of such graphs.
E.g.f.: -LambertW(exp(-x)-1). - Vladeta Jovovic (vladeta(AT)eunet.rs), Nov 22 2002
a(n) is asymptotic to sqrt(r*(e-1))/n*(n/e/r)^n where r=1-log(e-1)
a(n) = Sum_{k=0..n} Stirling2(n, k)*A060356(k). Also a(n) = Sum_{k=1..n} (-1)^(n-k)*Stirling2(n, k)*k^(k-1). - Vladeta Jovovic (vladeta(AT)eunet.rs), Sep 17 2003
|
|
CROSSREFS
|
Cf. A007134, A058864, A058865.
Cf. A048802.
Sequence in context: A089465 A106174 A056814 this_sequence A108953 A099869 A056785
Adjacent sequences: A058860 A058861 A058862 this_sequence A058864 A058865 A058866
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Robert Castelo (rcastelo(AT)imim.es), Jan 06 2001
|
|
|
Search completed in 0.002 seconds
|
