[seqfan] Re: Comment in A000792

[Jim Nastos]

Hi,
  You are correct (regarding the number of cliques) but I think the
comment should probably be corrected to a statement like "...the
maximum number of *maximal* cliques..."

  So then a complete graph has only 1 maximal clique. A path on n
vertices has n-1 maximal cliques. A cycle of size n has n maximal
cliques for n >= 4.

  On 5 vertices, a graph with 6 maximal cliques can be found:
Vertices: a,b,c,d,e
Edges: ba, be, bc, da, de, dc

The next term of '9' can be realized with a graph having a 6th vertex,
f, with edges fa, fe, fc in the graph above.

  So this could be the intended statement. If it is, it should be
further adjusted to say "n >= 4" instead of "n >= 2" since on 3
vertices we can not find a graph with 3 maximal cliques (the 3-cycle
happens to be clique.)

JN

On Tue, Mar 10, 2009 at 4:16 PM, Tanya Khovanova
<mathoflove-seqfan at yahoo.com> wrote:
>
> Hello SeqFans,
>
> I have a problem with the sequence A000792 a(n) = max{ (n-i)a(i) : i<n}; a(0) = 1. (Formerly M0568 N0205)
>        1, 1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54
>
> More precisely, not with the sequence, but with the comment:
> Also the maximum number of cliques possible in a graph with n vertices, for n >= 2 (cf. Capobianco and Molluzzo). - Felix Goldberg (felixg(AT)tx.technion.ac.il), Jul 15 2001
>
> Isn't the maximum number of cliques is 2^n - 1 and is achieved in the complete graph?
>
> Tanya
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>