A079565
Number of unlabeled and connected graphs on n vertices which are either bipartite or co-bipartite.
Original entry on oeis.org
1, 1, 2, 6, 16, 49, 129, 481, 1845, 9506, 57896, 463909, 4769436, 65179170, 1187099045, 29082860878, 960963147303, 42920936851975, 2594399793419459, 212465886865393053, 23596018831885668391, 3557502387712889568013, 728850489548729072323085
Offset: 1
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.
-
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]];
a /@ Range[1, 50] (* Jean-François Alcover, Sep 17 2019 *)
A236525
Number of simple non-bipartite graphs on n nodes.
Original entry on oeis.org
0, 0, 1, 4, 21, 121, 956, 12043, 273549, 11999689, 1018965561, 165090921457, 50502028840240, 29054155623249635, 31426485969192461828, 64001015704512693244004, 245935864153532444460997784, 1787577725145611678835828915650, 24637809253125004523074706811821299
Offset: 1
a(3) = 1 since the only non-bipartite graph on 3 vertices is the triangle.
A342212
Largest number of maximal bipartite node-induced subgraphs of an n-node graph.
Original entry on oeis.org
1, 1, 3, 6, 10, 15, 21, 38, 64
Offset: 1
All optimal graphs (i.e., graphs having n nodes and a(n) maximal bipartite subgraphs) for 1 <= n <= 9 are listed below. Here, FCB(n_1, ..., n_k) denotes the full cyclic braid graph with cluster sizes n_1, ..., n_k, as defined by Morrison and Scott (2017), i.e., the graph obtained by arranging complete graphs of orders n_1, ..., n_k (in that order) in a cycle, and joining all pairs of nodes in neighboring parts with edges. (The graph in the paper by Byskov, Madsen, and Skjernaa, which shows that a(10) >= 105, is FCB(2, 2, 2, 2, 2).)
n = 1: the 1-node graph;
n = 2: the complete graph and the empty graph;
3 <= n <= 6: the complete graph;
n = 7: FCB(1, 1, 2, 1, 2) (the Moser spindle) and the complete graph;
n = 8: FCB(1, 2, 1, 2, 2) and the 4-antiprism graph;
n = 9: FCB(1, 2, 2, 1, 3).
For a list of related sequences, see cross-references in
A342211.
A287512
Number of simple perfect non-bipartite graphs on n vertices.
Original entry on oeis.org
0, 0, 1, 4, 20, 113, 818, 8584, 135637, 3263785, 115779695, 5855248060
Offset: 1
Comments