|
|
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. 1-74.
|
|
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
|
|
|
|