login
Number of trivially-perfect graphs on n nodes.
4

%I #16 Nov 26 2015 09:01:30

%S 1,2,4,9,20,48,115,286,719,1842,4766,12486,32973,87811,235381,634847,

%T 1721159,4688676,12826228,35221832,97055181,268282855,743724984,

%U 2067174645,5759636510,16083734329,45007066269,126186554308,354426847597

%N Number of trivially-perfect graphs on n nodes.

%C Is this the same as A000081 with a different offset? - _N. J. A. Sloane_

%C Yes, because it equals the number of rooted forests with n nodes (see Golumbic reference). The Euler transform shifts this sequence by one. Thus the number of connected trivially-perfect graphs on n nodes is a(n-1). - _Falk Hüffner_, Nov 26 2015

%H M. C. Golumbic, <a href="http://dx.doi.org/10.1016/0012-365X(78)90178-4">Trivially perfect graphs</a>, Discr. Math. 24(1) (1978), 105-107.

%H S. Hougardy, <a href="http://www.or.uni-bonn.de/~hougardy/">Home Page</a>

%H S. Hougardy, <a href="http://dx.doi.org/10.1016/j.disc.2006.05.021">Classes of perfect graphs</a>, Discr. Math. 306 (2006), 2529-2571.

%F a(n) = A000081(n+1) - _Falk Hüffner_, Nov 26 2015

%Y Cf. A000081.

%K nonn

%O 1,2

%A _N. J. A. Sloane_, Oct 18 2006