|
|
A157015
|
|
Number of graphs with n vertices having a bipartite connected component.
|
|
3
|
|
|
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
|
|
|
FORMULA
|
|
|
MATHEMATICA
|
cbs[g_] := Or @@ Map[BipartiteQ, Map[InduceSubgraph[g, # ] &, ConnectedComponents[g]]] Table[Count[Map[cbs, ListGraphs[n]], True], {n, 7}]
In[2]:= Table[Count[Graphs[n], _?(Function[g,
Or @@ BipartiteQ /@ (InduceSubgraph[g, # ] & /@
ConnectedComponents[g])])], {n, 8}] // Timing
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|