

A086371


a(n) is the sum, over all labeled graphs G on n nodes, of the clique number w(G).


0




OFFSET

1,2


COMMENTS

The expected clique number of G(n,1/2) is the rational value a(n)/b(n), where b(n) denotes the sequence A006125 (the number of graphs on n labeled nodes). For instance, the expected clique number of G(4,1/2) is a(4)/b(4) = 151/64. G(n,1/2) denotes the random graph on n labeled nodes obtained by choosing, randomly and independently, every pair of nodes {ij} to be an edge with probability 1/2 (Alon, Krivelevich and Sudakov p. 2)


LINKS

I.M. Bomze, M. Budinich, P.M. Pardalos and M. Pelillo, The Maximum Clique Problem, Handbook of Combinatorial Optimization (supplement vol. A), D.Z. Du and P.M. Pardalos, eds. (1999), pp. 174.


EXAMPLE

Consider the 8 different labeled graphs on 3 nodes: one of the graphs has clique number 1, six of the graphs have clique number 2 and one of the graphs has clique number 3. Hence a(3) = 1*1 + 6*2 + 1*3 = 16.


CROSSREFS



KEYWORD

more,nice,nonn


AUTHOR

Tim Paulden (timmy(AT)cantab.net), Sep 05 2003


STATUS

approved



