[seqfan] Re: A157015: graphs with n vertices having a bipartite connected components

[Eric W. Weisstein]

On Sat, 2 May 2009, Edwin Clark wrote:

> Just trying out some of the new Maple 13 procedures which generate
> non isomorphic graphs of order n, etc, and I find for
> http://www.research.att.com/~njas/sequences/A157015
> that Maple disagrees with A157015(8). It agrees with all values from 0 to
> 9 except for a(8). It gives a(8) = 1389  which differs from the value of
> 1386 in the OEIS.  Could someone please check this. Looks like it could be
> a copying error. That or there is a problem in Maple 13.

A157015(8) is indeed incorrect.   a(8) = 1389 is correct.

In[1]:= <<Combinatorica`
In[2]:= Table[Count[Graphs[n], _?(Function[g,
       Or @@ BipartiteQ /@ (InduceSubgraph[g, #] & /@
           ConnectedComponents[g])])], {n, 8}] // Timing
Out[2]= {28.2611, {1, 2, 3, 8, 18, 60, 232, 1389}}

Cheers,
-Eric