

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

Table of n, a(n) for n=1..7.
N. Alon, M. Krivelevich and B. Sudakov, Finding a large hidden clique in a random graph, Proc. of the Ninth Annual ACMSIAM SODA, ACM Press (1998), pp. 594598. Also: Random Structures and Algorithms 13 (1998), pp. 457466.
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.
Eric Weisstein's World of Mathematics, Clique Number.


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

Cf. A052450, A052451, A052452, A077392, A077393, A077394, A006125.
Sequence in context: A230323 A217251 A125281 * A229954 A228513 A135753
Adjacent sequences: A086368 A086369 A086370 * A086372 A086373 A086374


KEYWORD

more,nice,nonn


AUTHOR

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


STATUS

approved



