A355335 -id:A355335 - cp's OEIS frontend

A355334 Triangle read by rows: T(n,k) is the number of unlabeled graphs with n nodes and bipartite dimension (or biclique covering number) k, 0 <= k < n.

1, 1, 1, 1, 2, 1, 1, 4, 6, 0, 1, 6, 20, 7, 0, 1, 9, 61, 80, 5, 0, 1, 12, 159, 650, 221, 1, 0, 1, 16, 381, 4710, 6866, 372, 0, 0, 1, 20, 832, 29921, 183618, 59950, 326, 0, 0

Offset: 1

Pontus von Brömssen, Jun 29 2022

			Triangle begins:
  n\k | 0  1   2     3      4     5   6  7  8
  ----+--------------------------------------
   1  | 1
   2  | 1  1
   3  | 1  2   1
   4  | 1  4   6     0
   5  | 1  6  20     7      0
   6  | 1  9  61    80      5     0
   7  | 1 12 159   650    221     1   0
   8  | 1 16 381  4710   6866   372   0  0
   9  | 1 20 832 29921 183618 59950 326  0  0

Wikipedia, Bipartite dimension

Cf. A000088 (row sums), A355333, A355335, A355336.

Columns: A000012 (k=0), A002620 (k=1).

A355336 Number of unlabeled n-node graphs with the largest possible bipartite dimension (or biclique covering number).

Original entry on oeis.org

1, 1, 1, 6, 7, 5, 1, 372, 326

Offset: 1

Pontus von Brömssen, Jun 29 2022

Let b(n) be the largest bipartite dimension of an n-node graph. Then b(n) >= A057359(n). If, for all n >= 8, there exists a disconnected n-node graph with bipartite dimension b(n), then b(n) = A057359(n) for all n >= 1. Proof: Since the bipartite dimension of a graph equals the sum of the bipartite dimensions of its connected components, we have that b(n) >= max_{k=1..n-1} b(k)+b(n-k) (i.e., the sequence is superadditive), with equality if there exists a disconnected n-node graph with bipartite dimension b(n). It is easily checked that A057359(n) = max_{k=1..n-1} A057359(k)+A057359(n-k) for n >= 8. Since b(n) = A057359(n) for 1 <= n <= 7 (checked by brute force), the result follows.
Since (b(n)) is superadditive, it follows from Fekete's subadditive lemma that the limit of b(n)/n exists and equals the supremum of b(n)/n. It is easy to see that b(n) <= b(n-1) + 1, so this limit is between 5/7 = b(7)/7 and 1.
The numbers of disconnected n-node graphs with bipartite dimension b(n) for 1 <= n <= 9 are 0, 0, 0, 2, 1, 1, 0, 12, 6.

Wikipedia, Bipartite dimension

Cf. A057359, A355334, A355335.

cp's OEIS Frontend

A355334 Triangle read by rows: T(n,k) is the number of unlabeled graphs with n nodes and bipartite dimension (or biclique covering number) k, 0 <= k < n.

Views

Author

Keywords

Examples

Links

Crossrefs