A371161 -id:A371161 - cp's OEIS frontend

A000717 Number of graphs with n nodes and floor(n(n-1)/4) edges.

1, 1, 1, 3, 6, 24, 148, 1646, 34040, 1358852, 106321628, 16006173014, 4525920859198, 2404130854745735, 2426376196165902704, 4648429222263945620900, 16788801124652327714275292, 114722035311851620271616102401

Offset: 1

N. J. A. Sloane

This is the largest number of graphs with n vertices that all have the same number of edges. a(n) <= A371161(n). - Allan Bickle, Apr 18 2024

			There are three graphs with 4 vertices and 3 edges, K_3 U K_1, K_{1,3}, and P_4, so a(4) = 3. - _Allan Bickle_, Apr 18 2024

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 146.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Sean A. Irvine, Table of n, a(n) for n = 1..40
M. L. Stein and P. R. Stein, Enumeration of Linear Graphs and Connected Linear Graphs up to p = 18 Points. Report LA-3775, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Oct 1967

Cf. A008406, A371161.

More terms from Sean A. Irvine, Mar 10 2011

A371162 Largest possible number of minimal forbidden subgraphs for a graph of order n.

Original entry on oeis.org

1, 1, 2, 2, 4, 5, 13, 33, 149

Offset: 0

Allan Bickle and Max Alekseyev, Mar 13 2024

a(n) <= A371161(n) + 1.

Max A. Alekseyev and Allan Bickle, Forbidden Subgraphs of Single Graphs, (2024). See p. 17.

A376782 Triangle read by rows: T(n,m) is the number of unlabeled graphs with n vertices having m minimum forbidden subgraphs, n >= 1, 1 <= m <= A371162(n).

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 4, 4, 2, 1, 4, 8, 13, 8, 1, 4, 5, 7, 20, 34, 31, 28, 12, 8, 5, 0, 1, 1, 4, 5, 13, 26, 33, 43, 59, 50, 62, 58, 60, 64, 67, 63, 70, 68, 65, 61, 60, 31, 28, 16, 8, 13, 4, 4, 4, 0, 2, 1, 0, 1, 1, 4, 6, 9, 21, 34, 39, 71, 74, 77, 99, 118, 124, 107, 129

Offset: 1

Max Alekseyev, Oct 03 2024

			Triangle starts with
n = 1: 1
n = 2: 1 1
n = 3: 1 3
n = 4: 1 4 4  2
n = 5: 1 4 8 13  8
n = 6: 1 4 5  7 20 34 31 28 12 8 5 0 1
...

Max Alekseyev, Table of k, a(k) for k = 1..209 (rows n = 1..8 flattened)
Max A. Alekseyev and Allan Bickle, Forbidden Subgraphs of Single Graphs, 2024.

Cf. A000088 (row sums), A371162 (row lengths), A000012 (column m=1), A113311 (column m=2).

Cf. A002865, A006897, A103221, A371161, A376780, A376781.

A376780 Triangular table read by rows: T(n,k) is the minimum number of minimal forbidden subgraphs of a graph with n vertices and k edges, n >= 1, 0 <= k <= n*(n-1)/2.

Original entry on oeis.org

1, 2, 1, 2, 2, 2, 1, 2, 3, 2, 3, 2, 2, 1, 2, 3, 2, 3, 3, 4, 3, 3, 2, 2, 1, 2, 3, 3, 2, 4, 3, 4, 5, 5, 4, 5, 5, 4, 2, 2, 1, 2, 3, 3, 2, 4, 4, 3, 4, 5, 4, 5, 5, 7, 6, 6, 5, 5, 4, 4, 2, 2, 1, 2, 3, 3, 3, 2, 4, 4, 3, 5, 6, 5, 6, 5, 5, 7, 6, 7, 10, 9, 9, 9, 8, 10, 5, 5, 4, 2, 2, 1

Offset: 1

Max Alekseyev, Oct 03 2024

			Table starts with
n = 1: 1
n = 2: 2, 1
n = 3: 2, 2, 2, 1
n = 4: 2, 3, 2, 3, 2, 2, 1
...

Max A. Alekseyev and Allan Bickle, Forbidden Subgraphs of Single Graphs, 2024.

Cf. A002865, A006897, A103221, A371161, A371162, A376781, A376782.

A376781 Triangular table read by rows: T(n,k) is the maximum number of minimal forbidden subgraphs of a graph with n vertices and k edges, n >= 1, 0 <= k <= n*(n-1)/2.

Original entry on oeis.org

1, 2, 1, 2, 2, 2, 1, 2, 3, 4, 4, 3, 2, 1, 2, 3, 4, 5, 5, 5, 5, 4, 3, 2, 1, 2, 3, 4, 6, 8, 8, 9, 13, 11, 11, 9, 6, 5, 3, 2, 1, 2, 3, 4, 6, 8, 8, 11, 16, 20, 23, 28, 31, 30, 33, 24, 22, 15, 10, 7, 3, 2, 1, 2, 3, 4, 6, 8, 9, 14, 21, 24, 31, 41, 57, 78, 86, 106, 123, 134, 149, 143, 138, 133, 75, 46, 37, 18, 11, 3, 2, 1

Offset: 1

Max Alekseyev, Oct 03 2024

			Table starts with
n = 1: 1
n = 2: 2, 1
n = 3: 2, 2, 2, 1
n = 4: 2, 3, 4, 4, 3, 2, 1
...

Max A. Alekseyev and Allan Bickle, Forbidden Subgraphs of Single Graphs, 2024.

Cf. A371162 (row maximums).

Cf. A002865, A006897, A103221, A371161, A376780, A376782.

cp's OEIS Frontend

A000717 Number of graphs with n nodes and floor(n(n-1)/4) edges.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A371162 Largest possible number of minimal forbidden subgraphs for a graph of order n.

Views

Author

Keywords

Comments

Links

A376782 Triangle read by rows: T(n,m) is the number of unlabeled graphs with n vertices having m minimum forbidden subgraphs, n >= 1, 1 <= m <= A371162(n).

Views

Author

Keywords

Examples

Links

Crossrefs

A376780 Triangular table read by rows: T(n,k) is the minimum number of minimal forbidden subgraphs of a graph with n vertices and k edges, n >= 1, 0 <= k <= n*(n-1)/2.

Views

Author

Keywords

Examples

Links

Crossrefs

A376781 Triangular table read by rows: T(n,k) is the maximum number of minimal forbidden subgraphs of a graph with n vertices and k edges, n >= 1, 0 <= k <= n*(n-1)/2.

Views

Author

Keywords

Examples

Links

Crossrefs