

A157015


Number of graphs with n vertices having a bipartite connected component.


1



0, 1, 2, 3, 8, 18, 60, 232, 1389, 14174, 291396, 12307993, 1031244083, 166112993730, 50667178220215, 29104660317374991, 31455540471012663839, 64032442292149795841796, 245999865227419158171980939, 1787823661072649054474456291897, 24639596830978183991220162941946112
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


LINKS

Table of n, a(n) for n=0..20.
Tanya Khovanova, Can Someone Be Straight? [From Tanya Khovanova, Sep 23 2009]


FORMULA

a(n) = A000088(n)  A157016(n).


MATHEMATICA

cbs[g_] := Or @@ Map[BipartiteQ, Map[InduceSubgraph[g, # ] &, ConnectedComponents[g]]] Table[Count[Map[cbs, ListGraphs[n]], True], {n, 7}]
(* from Eric W. Weisstein, May 02 2009: *) First do: <<Combinatorica
In[2]:= Table[Count[Graphs[n], _?(Function[g,
Or @@ BipartiteQ /@ (InduceSubgraph[g, # ] & /@
ConnectedComponents[g])])], {n, 8}] // Timing


CROSSREFS

Sequence in context: A158448 A073192 A113183 * A240645 A273754 A242099
Adjacent sequences: A157012 A157013 A157014 * A157016 A157017 A157018


KEYWORD

nonn


AUTHOR

Tanya Khovanova, Feb 21 2009


EXTENSIONS

Incorrect comment deleted by N. J. A. Sloane, Feb 22 2009
Terms from a(8) onwards from Max Alekseyev, Feb 22 2009
Offset corrected by Max Alekseyev, Feb 24 2009
a(8) corrected by W. Edwin Clark, May 02 2009; confirmed by Eric W. Weisstein
Corrected by Max Alekseyev and Vladeta Jovovic, May 02 2009
a(18)a(20) from Max Alekseyev, Jun 24 2013


STATUS

approved



