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

0, 1, 2, 3, 8, 18, 60, 232, 1389, 14174, 291396, 12307993, 1031244083, 166112993730, 50667178220215, 29104660317374991, 31455540471012663839, 64032442292149795841796, 245999865227419158171980939, 1787823661072649054474456291897, 24639596830978183991220162941946112

Offset

0,3

Links

Andrew Howroyd, Table of n, a(n) for n = 0..50

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: A073192 A317722 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