# [seqfan] comments Re: Need help with graph sequences

Tanya Khovanova mathoflove-seqfan at yahoo.com
Sun Feb 22 18:23:49 CET 2009

```Thank you all for your help with these sequences.

Formally, my comment for A157015 was correct that in such a graph there exists a vertex that doesn't belong to a cycle of odd length.

But Brendan's comment is much better because it includes my comment and it is an equivalent definition.

The comment for A157015 should be:
These are graphs for which there exists a vertex not connected to a cycle of odd length.

The comment that I had for A157016 is correct:
These are graphs such that any vertex is connected to a cycle of odd length.

Tanya

--- On Sun, 2/22/09, Brendan McKay <bdm at cs.anu.edu.au> wrote:

> From: Brendan McKay <bdm at cs.anu.edu.au>
> Subject: Re: [seqfan]  Need help with graph sequences
> To: seqfan at list.seqfan.eu
> Cc: mathoflove-seqfan at yahoo.com
> Date: Sunday, February 22, 2009, 12:02 AM
> > From: Tanya Khovanova
> <mathoflove-seqfan at yahoo.com>
> >
> > Hello SeqFans,
> >
> > I just submitted two sequences below. My inefficient
> program counts only the first 6 terms. The problem is that
> the second sequence exists in the OEIS, but I do not have
> any good reasons to believe that it is the same as mine, I
> need the next term to make sure. Can you do that?
> >
> > %S A157015 1,2,3,8,18,60
> > %N A157015 Number of graphs with n vertices, such that
> a bipartite connected component exists.
> > %C A157015 There exists a vertex which doesn't
> belong to a cycle of odd length.
>
> These two definitions are not the same.  Are they supposed
> to be?
> Maybe you should write "..which isn't connected to
> a cycle of odd
> length".
>
> Brendan.
>
>
> > %S A157016 0,0,1,3,16,96
> > %N A157016 Number of graphs with n vertices such that
> a bipartite connected component doesn't exist.
> > %C A157016 Any vertex is connected to a cycle of odd
> length.
> > %t A157016 cbs[g_] := Or @@ Map[BipartiteQ,
> Map[InduceSubgraph[g, #] &, ConnectedComponents[g]]]
> Table[Count[Map[cbs, ListGraphs[n]], False], {n, 6}]
> >
> > Thank you in advance,
> > Tanya

```