A005142 -id:A005142 - cp's OEIS frontend

A318590 Number of connected balanced simple signed graphs on n unlabeled nodes.

1, 1, 2, 5, 28, 177, 1982, 33997, 1020516, 54570672, 5347070228, 967135763525, 324200029119318, 202046821340636691, 234878262433630160622, 511060736355598412146405, 2088401066728281847415734793, 16079824271822965645002329491423, 233994776259866281916838227225733732

Offset: 0

Andrew Howroyd, Sep 25 2018

nonn

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

Cf. A005142, A034892, A053465, A054919, A054921.

a(2*n+1) = A054921(2*n+1)/2, a(2*n) = (a(n) + A054919(n) + A054921(2*n) - A054921(n))/2.

Inverse Euler transform of A034892.

A034892 Number of balanced signed graphs on n unlabeled nodes.

Original entry on oeis.org

1, 1, 3, 8, 39, 226, 2283, 36789, 1062679, 55717077, 5405078682, 972656526492, 325183692812200, 202373967993972497, 235081289816026793049, 511296223391186047847309, 2088912833728676472658628201, 16081914207958884651686215477871, 234010862353438997655954463710225233

Offset: 0

Ronald C. Read

R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.

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

Cf. A004102, A005142, A318590.

Euler transform of A318590.

Name clarified and offset corrected by Andrew Howroyd, Sep 25 2018

a(0)=1 prepended and terms a(13) and beyond from Andrew Howroyd, Sep 25 2018

A079571 Number of unlabeled, connected graphs on n vertices whose complements are bipartite.

Original entry on oeis.org

1, 1, 1, 2, 5, 11, 32, 85, 299, 1115, 5474, 32298, 251129, 2527706, 33985846, 611846933, 14864650916, 488222721984, 21712049275189, 1308300679611460, 106897965189674281, 11852113048215107812, 1784730721403509209204, 365323537513403184463262

Offset: 0

Jim Nastos, Jan 24 2003

nonn

Equivalently, number of bipartite graphs whose complement is connected. The only bipartite graphs with disconnected complement are complete bipartite graphs. - Falk Hüffner, Jan 22 2016

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

Cf. A005142, A033995.

A005142 = Import["https://oeis.org/A005142/b005142.txt", "Table"][[All, 2]];
etr[p_] := Module[{b}, b[n_] := b[n] = If[n == 0, 1, Sum[Sum[d*p[d], {d, Divisors[j]}]*b[n - j], {j, 1, n}]/n]; b];
b = etr[A005142[[# + 1]]&];
a[n_] := b[n] - Floor[n/2];
a /@ Range[0, 50] (* Jean-François Alcover, Sep 17 2019 *)

a(n) = A033995(n) - floor(n/2).

Corrected and extended using formula by Falk Hüffner, Jan 22 2016

a(0)=1 prepended and terms a(21) and beyond from Andrew Howroyd, Sep 05 2018

A369227 Triangle read by rows: T(n,k) is the number of uniquely colorable simple graphs on n nodes with chromatic number k = 1..n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 5, 3, 1, 1, 1, 17, 12, 3, 1, 1, 1, 44, 72, 12, 3, 1, 1, 1, 182, 856, 127, 12, 3, 1, 1, 1, 730, 17018, 3426, 127, 12, 3, 1, 1, 1, 4032, 531568, 221188, 4938, 127, 12, 3, 1, 1, 1, 25598

Offset: 1

Eric W. Weisstein, Jan 16 2024

			Triangle read by rows:
  1
  1,     1
  1,     1,      1
  1,     3,      1,      1
  1,     5,      3,      1,    1
  1,    17,     12,      3,    1,   1
  1,    44,     72,     12,    3,   1,  1
  1,   182,    856,    127,   12,   3,  1, 1
  1,   730,  17018,   3426,  127,  12,  3, 1, 1
  1,  4032, 531568, 221188, 4938, 127, 12, 3, 1, 1
  1, 25598,    ...

Eric Weisstein's World of Mathematics, Chromatic Number.
Eric Weisstein's World of Mathematics, Simple Graph.
Eric Weisstein's World of Mathematics, Uniquely Colorable Graph.

Cf. A005142, A348222, A369223.

T(n,1) = 1.
T(n,2) = A005142(n).
T(n,3) = A348222(n).
T(n,n) = 1.
Sum_{k=1..n} T(n,k) = A369223(n).

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

Jim Nastos, Jan 24 2003

nonn

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

			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.

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

Cf. A005142, A079571.

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 *)

For n >= 5, a(n) = A079571(n) + A005142(n). - Falk Hüffner, Jan 22 2016

More terms using formula by Falk Hüffner, Jan 22 2016

Terms a(21) and beyond from Andrew Howroyd, Sep 05 2018

A165452 Number of connected graphs of odd girth at least 7 with n vertices.

Original entry on oeis.org

1, 1, 1, 3, 5, 17, 45, 184, 748, 4143, 26532, 221032, 2326853, 32202266, 589436301, 14459238676, 477812658943

Offset: 1

Friedrich Regen (friedrich.regen(AT)tu-ilmenau.de), Sep 20 2009

nonn

The odd girth of a graph is the length of a shortest cycle of odd length. Thus, these are the connected graphs that do not have a triangle or C_5 as induced subgraph. - Falk Hüffner, Jan 15 2016

The bipartite graphs (which have no odd cycles) are included.

F. Hüffner, tinygraph, software for generating integer sequences based on graph properties, version ece94ef.

Cf. A005142, A024607.

Inverse EULER transform of A345247.

a(15) and a(16) added using tinygraph by Falk Hüffner, Jan 15 2016

a(17) added by Brendan McKay, Jun 12 2021

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

Pontus von Brömssen, Mar 05 2021

This sequence is log-superadditive, i.e., a(m+n) >= a(m)*a(n). By Fekete's subadditive lemma, it follows that the limit of a(n)^(1/n) exists and equals the supremum of a(n)^(1/n). - Pontus von Brömssen, Mar 03 2022

Byskov, Madsen, and Skjernaa (2005) construct a 10-node graph with 105 maximal bipartite subgraphs, so a(10) >= 105.

			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).

Jesper Makholm Byskov, Bolette Ammitzbøll Madsen, and Bjarke Skjernaa, On the number of maximal bipartite subgraphs of a graph, Journal of Graph Theory 48 (2005), 127-132.
Natasha Morrison and Alex Scott, Maximising the number of induced cycles in a graph, Journal of Combinatorial Theory Series B 126 (2017), 24-61.

Cf. A005142, A033995.

For a list of related sequences, see cross-references in A342211.

a(m+n) >= a(m)*a(n).
a(n) <= n*12^(n/4). (Byskov, Madsen, and Skjernaa (2005))
1.5926... = 105^(1/10) <= lim_{n->oo} a(n)^(1/n) <= 12^(1/4) = 1.8612... . (Byskov, Madsen, and Skjernaa (2005))

A128953 Number of 3-connected bipartite graphs on n unlabeled nodes.

Original entry on oeis.org

1, 1, 6, 12, 85, 471, 5373, 75145, 1543382, 41554738

Offset: 6

Gordon F. Royle, May 10 2007

			a(6) = 1 because the complete bipartite graph K_{3,3} is the only 3-connected bipartite graph on 6 vertices.

Cf. A005142.

A243270 Number of unlabeled simple graphs with n nodes that are Hamiltonian and bipartite.

Original entry on oeis.org

1, 0, 0, 1, 0, 4, 0, 24, 0, 473, 0, 30512, 0, 6374556

Offset: 1

Travis Hoppe and Anna Petrone, Jun 02 2014

Travis Hoppe and Anna Petrone, Encyclopedia of Finite Graphs.
Travis Hoppe and Anna Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644 [math.CO], 2014.
Falk Hüffner, tinygraph, software for generating integer sequences based on graph properties, version 4361e42
Eric Weisstein's World of Mathematics, Bipartite Graph.
Eric Weisstein's World of Mathematics, Hamiltonian Graph.

Cf. A003216 (Hamiltonian graphs), A005142 (bipartite graphs).

a(11)-a(14) added using tinygraph by Falk Hüffner, Aug 13 2017

A243320 Number of simple connected graphs with n nodes that are bipartite and Eulerian.

Original entry on oeis.org

1, 0, 0, 1, 0, 2, 1, 6, 7, 29, 64, 287, 1148, 7267, 55997, 620561

Offset: 1

Travis Hoppe and Anna Petrone, Jun 03 2014

Travis Hoppe and Anna Petrone, Encyclopedia of Finite Graphs
T. Hoppe and A. Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644 [math.CO], 2014.
F. Hüffner, tinygraph, software for generating integer sequences based on graph properties, version 69d4186

Cf. A005142 (bipartite graphs), A003049 (Eulerian graphs).

a(11)-a(16) added using tinygraph by Falk Hüffner, Jan 15 2016

cp's OEIS Frontend

A318590 Number of connected balanced simple signed graphs on n unlabeled nodes.

Views

Author

Keywords

Links

Crossrefs

Formula

A034892 Number of balanced signed graphs on n unlabeled nodes.

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

A079571 Number of unlabeled, connected graphs on n vertices whose complements are bipartite.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A369227 Triangle read by rows: T(n,k) is the number of uniquely colorable simple graphs on n nodes with chromatic number k = 1..n.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A079565 Number of unlabeled and connected graphs on n vertices which are either bipartite or co-bipartite.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A165452 Number of connected graphs of odd girth at least 7 with n vertices.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A342212 Largest number of maximal bipartite node-induced subgraphs of an n-node graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A128953 Number of 3-connected bipartite graphs on n unlabeled nodes.

Views

Author

Keywords

Examples

Crossrefs

A243270 Number of unlabeled simple graphs with n nodes that are Hamiltonian and bipartite.

Views

Author

Keywords

Links

Crossrefs

Extensions

A243320 Number of simple connected graphs with n nodes that are bipartite and Eulerian.

Views