login
Number of bipartite graphs with n nodes.
25

%I #66 Sep 05 2023 01:54:34

%S 1,1,2,3,7,13,35,88,303,1119,5479,32303,251135,2527712,33985853,

%T 611846940,14864650924,488222721992,21712049275198,1308300679611469,

%U 106897965189674291,11852113048215107822,1784730721403509209215,365323537513403184463273

%N Number of bipartite graphs with n nodes.

%C All bipartite graphs are perfect. - _Falk Hüffner_, Nov 27 2015

%C EULER transform of A005142 [1, 1, 1, 3, 5, 17, ...] is [1, 2, 3, 7, 13, ...]. - _Michael Somos_, May 13 2019

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

%H Andrew Howroyd, <a href="/A033995/b033995.txt">Table of n, a(n) for n = 0..50</a>

%H CombOS - Combinatorial Object Server, <a href="http://combos.org/nauty">Generate graphs</a>.

%H P. Erdős, D. J. Kleitman, and B. L. Rothschild, <a href="https://users.renyi.hu/~p_erdos/1976-03.pdf">Asymptotic enumeration of k_n-free graphs</a>. In Colloquio Internazionale sulle Teorie Combinatorie, (Rome, 1973), Tomo II, Atti dei Convegni Lincei, No. 17, pp. 19-27. Accad. Naz. Lincei, Rome.

%H P. Hanlon, <a href="http://dx.doi.org/10.1016/0012-365X(79)90184-5">The enumeration of bipartite graphs</a>, Discrete Math. 28 (1979), 49-57.

%H S. Hougardy, <a href="http://www.or.uni-bonn.de/~hougardy/">Home Page</a>.

%H S. Hougardy, <a href="http://dx.doi.org/10.1016/j.disc.2006.05.021">Classes of perfect graphs</a>, Discr. Math. 306 (2006), 2529-2571.

%H Sage, <a href="http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_generators.html">Common Graphs (Graph Generators)</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/BipartiteGraph.html">Bipartite Graph</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/BicolorableGraph.html">Bicolorable Graph</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/n-ColorableGraph.html">n-Colorable Graph</a>.

%e For n=1: o; n=2: o o, o-o; n=3: o o o, o o-o, o-o-o; n=4: o o o o, o o o-o, o-o o-o, o o-o-o, o-o-o-o, K_{2,2}, K_{3,1}. - _Michael Somos_, May 13 2019

%t A005142 = Cases[Import["https://oeis.org/A005142/b005142.txt", "Table"], {_, _}][[All, 2]];

%t (* EulerTransform is defined in A005195 *)

%t EulerTransform[Rest @ A005142] (* _Jean-François Alcover_, Mar 18 2020 *)

%Y Row sums of A297877.

%Y The labeled version is A047864.

%Y Equals A076278(n) + 1.

%Y Cf. A005142 (connected).

%K nonn,nice

%O 0,3

%A Ronald C. Read

%E a(0)=1 prepended and terms a(21) and beyond from _Andrew Howroyd_, Sep 05 2018