A157051 -id:A157051 - cp's OEIS frontend

A157016 Number of graphs with n vertices such that a bipartite connected component doesn't exist.

1, 0, 0, 1, 3, 16, 96, 812, 10957, 260494, 11713772, 1006689871, 164059928509, 50335918374222, 29003488479015273, 31397381309486933777, 63969560164056545231089, 245871831711240782887877980, 1787331725280384281389706209909, 24636021429463931875328533035140871, 645465483198968863672173418327800803328

Offset: 0

Tanya Khovanova, Feb 21 2009

nonn

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

Cf. A000088, A157015, A157051.

cbs[g_] := Or @@ Map[BipartiteQ, Map[InduceSubgraph[g, # ] &, ConnectedComponents[g]]] Table[Count[Map[cbs, ListGraphs[n]], False], {n, 6}]
Table[Count[Map[cbs, ListGraphs[n]], False], {n,7}] (* Wouter Meeussen, Feb 21 2009 *)

Euler transform of A157051. - Max Alekseyev, Feb 22 2009

A157015(n) + a(n) = A000088(n).

a(7) from Wouter Meeussen, Feb 21 2009
Formula and terms a(8)-a(17) from Max Alekseyev, Feb 22 2009
Corrected by Max Alekseyev and Vladeta Jovovic, May 02 2009
a(18)-a(20) from Max Alekseyev, Jun 24 2013

A332964 Triangle read by rows: T(n,k) is the number of unlabeled simple graphs on n nodes with exactly k bipartite connected components, n >= 0, 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 3, 4, 2, 1, 1, 16, 9, 5, 2, 1, 1, 96, 37, 13, 6, 2, 1, 1, 812, 162, 46, 14, 6, 2, 1, 1, 10957, 1120, 194, 50, 15, 6, 2, 1, 1, 260494, 12675, 1219, 204, 51, 15, 6, 2, 1, 1, 11713772, 276758, 13099, 1254, 208, 52, 15, 6, 2, 1, 1

Offset: 0

Geoffrey Critzer, Mar 04 2020

T(n,k) is the number of graphs on n nodes with incidence matrix of rank n-k, where the incidence matrix is defined as in Godsil-Royle reference below.

			Triangle T(n,k) begins:
    1;
    0,   1;
    0,   1,   1;
    1,   1,   1,  1;
    3,   4,   2,  1,  1;
   16,   9,   5,  2,  1, 1;
   96,  37,  13,  6,  2, 1, 1;
  812, 162,  46, 14,  6, 2, 1, 1;
  ...

C. Godsil and G. Royle, Algebraic Graph Theory, Springer, 2001, page 166.

Cf. A157051 (column k=0 for n>0), A000088 (row sums), A157015, A005142.

Needs["Combinatorica`"];
Table[Table[Count[Prepend[Flatten[Table[g = {n, k};b = GraphData[g,"IncidenceMatrix"]; {n - MatrixRank[b]}, {k,2, NumberOfGraphs[n]}]], n], i], {i, 0, n}], {n, 0,7}] // Grid

G.f.: Product_{i>=1} (1/(1-x^i))^A157051(i)*(1/(1-y*x^i))^A005142(i).

cp's OEIS Frontend

A157016 Number of graphs with n vertices such that a bipartite connected component doesn't exist.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions