|
| |
|
|
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.
|
|
4
| |
|
|
1, 1, 4, 23, 181, 1812, 22037, 315569, 5201602, 97009833, 2019669961, 46432870222, 1168383075471, 31939474693297, 942565598033196, 29866348653695203, 1011335905644178273, 36446897413531401020
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,3
|
|
|
COMMENTS
| A subclass of chordal-comparability graphs.
|
|
|
REFERENCES
| M. C. Golumbic (1978) Trivially perfect graphs, Discrete Mathematics, 24:105-107.
Guruswami, Venkatesan, Enumerative aspects of certain subclasses of perfect graphs. Discrete Math. 205 (1999), 97-117. See p. 111.
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 * A192840 A186117 A108953
Adjacent sequences: A058860 A058861 A058862 * A058864 A058865 A058866
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Robert Castelo (rcastelo(AT)imim.es), Jan 06 2001
|
| |
|
|
