[seqfan] Re: Comment in A000792

[Tanya Khovanova]

That was my first thought, that a(n) is the maximum number of maximal cliques in the graph with n+2 vertices.

What about n=2? If we take a graph without edges, is an isolated vertex counted as a clique?


--- On Tue, 3/10/09, Jim Nastos <nastos at gmail.com> wrote:

> From: Jim Nastos <nastos at gmail.com>
> Subject: [seqfan] Re: Comment in A000792
> To: "Sequence Fanatics Discussion list" <seqfan at list.seqfan.eu>
> Date: Tuesday, March 10, 2009, 7:42 PM
> 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/
> >
> 
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/