|
|
A079565
|
|
Number of unlabeled and connected graphs on n vertices which are either bipartite or co-bipartite.
|
|
1
|
|
|
1, 1, 2, 6, 16, 49, 129, 481, 1845, 9506, 57896, 463909, 4769436, 65179170, 1187099045, 29082860878, 960963147303, 42920936851975, 2594399793419459, 212465886865393053, 23596018831885668391, 3557502387712889568013, 728850489548729072323085
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
G is bipartite iff the vertices can be partitioned into two sets such that all the edges in the graph go from one of these sets to the other. G is cobipartite iff the complement of G is bipartite.
For n >= 5, no graph can be both bipartite and co-bipartite. - Falk Hüffner, Jan 22 2016
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
Let G be a graph with 5 vertices, 4 of which form a path and the 5th adjacent only to the two vertices in the middle of the path. Then G is not bipartite nor cobipartite because there is a triangle in both G and its complement.
|
|
MATHEMATICA
|
A005142 = Import["https://oeis.org/A005142/b005142.txt", "Table"][[All, 2]];
A033995 = Import["https://oeis.org/A033995/b033995.txt", "Table"][[All, 2]];
a[n_] := If[n<5, {1, 1, 2, 6}[[n]], A005142[[n+1]] + A033995[[n+1]] - Floor[n/2]];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|