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

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

Offset

1,4

Comments

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.

Links

Table of n, a(n) for n=1..9.

Wikipedia, Bipartite dimension

Crossrefs

Cf. A057359, A355334, A355335.

Sequence in context: A305328 A332396 A100124 * A190648 A201519 A198507

Adjacent sequences: A355333 A355334 A355335 * A355337 A355338 A355339

Keyword

nonn,more

Author

Pontus von Brömssen, Jun 29 2022

Status

approved