The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A355336 Number of unlabeled n-node graphs with the largest possible bipartite dimension (or biclique covering number). 2
 1, 1, 1, 6, 7, 5, 1, 372, 326 (list; graph; refs; listen; history; text; internal format)
 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 18 15:14 EDT 2024. Contains 376000 sequences. (Running on oeis4.)