A005142 Number of connected bipartite graphs with n nodes.

1, 1, 1, 1, 3, 5, 17, 44, 182, 730, 4032, 25598, 212780, 2241730, 31193324, 575252112, 14218209962, 472740425319, 21208887576786, 1286099113807999, 105567921675718772, 11743905783670560579, 1772771666309380358809, 363526952035325887859823, 101386021137641794979558045

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• nice

Comments

Also, the number of unlabeled connected bicolored graphs having n nodes; the color classes may be interchanged. - Robert W. Robinson

Also, for n>1, number of connected triangle-free graphs on n nodes with chromatic number 2. - Keith M. Briggs, Mar 21 2006 (cf. A116079).

Also, first diagonal of triangle in A126736.

EULER transform of [1, 1, 1, 3, 5, 17, ...] is A033995 [1, 2, 3, 7, 13, ...]. - Michael Somos, May 13 2019

References

• R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
• R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..50
• Jean-François Alcover, Mathematica program
• Keith M. Briggs, Combinatorial Graph Theory
• CombOS - Combinatorial Object Server, Generate graphs
• P. Hanlon, The enumeration of bipartite graphs, Discrete Math. 28 (1979), 49-57.
• Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
• Eric Weisstein's World of Mathematics, Bipartite Graph.
• Eric Weisstein's World of Mathematics, n-Chromatic Graph
• Eric Weisstein's World of Mathematics, n-Colorable Graph
• Jonathan Wurtz and Danylo Lykov, The fixed angle conjecture for QAOA on regular MaxCut graphs, arXiv:2107.00677 [quant-ph], 2021.

Crossrefs

Cf. A033995, A116079, A318869, A318870.

Programs

Mathematica

(* See the links section. *)

Formula

a(2*n+1) = A318870(2*n+1)/2, a(2*n) = (a(n) + A318869(n) + A318870(2*n) - A318870(n))/2. - Andrew Howroyd, Sep 04 2018

Extensions

More terms from Ronald C. Read.

a(0)=1 prepended by Max Alekseyev, Jun 24 2013

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