The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A086371 a(n) is the sum, over all labeled graphs G on n nodes, of the clique number w(G). 0
1, 3, 16, 151, 2750, 97829, 6803239 (list; graph; refs; listen; history; text; internal format)



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)


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 ACM-SIAM SODA, ACM Press (1998), pp. 594-598. Also: Random Structures and Algorithms 13 (1998), pp. 457-466.

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.

Eric Weisstein's World of Mathematics, Clique Number.


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.


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




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



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 23 08:40 EDT 2021. Contains 348211 sequences. (Running on oeis4.)