A300756 -id:A300756 - cp's OEIS frontend

A006786 Number of squarefree graphs on n vertices.

1, 2, 4, 8, 18, 44, 117, 351, 1230, 5069, 25181, 152045, 1116403, 9899865, 104980369, 1318017549, 19427531763, 333964672216, 6660282066936

Offset: 1

N. J. A. Sloane

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

CombOS - Combinatorial Object Server, Generate graphs
Brendan McKay, Emails to N. J. A. Sloane, 1991
B. D. McKay, Isomorph-free exhaustive generation, J Algorithms, 26 (1998) 306-324.
S. Uijlen, B. Westerbaan, A Kochen-Specker system has at least 22 vectors, arXiv preprint arXiv:1412.8544 [cs.DM], 2014.
S. Uijlen and B. Westerbaan, A Kochen-Specker System Has at Least 22 Vectors, New Generation Computing, Vol. 34, No. 1-2 (2016), 3-23.
Eric Weisstein's World of Mathematics, Square-Free Graph
Index entries for sequences of squarefree graphs

Cf. A000088, A077269 (connected), A345249 (labeled), A039751 (complement). Row sums of A300756.

2 more terms (from the McKay paper) from Vladeta Jovovic, May 17 2008

2 more terms from Brendan McKay, Mar 11 2018

A191965 A problem of Zarankiewicz: maximal number of 1's in a symmetric n X n matrix of 0's and 1's with 0's on the main diagonal and no "rectangle" with 1's at the four corners.

Original entry on oeis.org

0, 2, 6, 8, 12, 14, 18, 22, 26, 32, 36, 42, 48, 54, 60, 66, 72, 78, 84, 92, 100, 104, 112, 118, 126, 134, 142, 152, 160, 170, 180, 184, 192, 204, 212, 220, 226, 234, 244, 254

Offset: 1

R. H. Hardin and N. J. A. Sloane, Jun 18 2011

In other words, the pattern
1...1
.....
1...1
is forbidden.
Such matrices are adjacency matrices of squarefree graphs (cf. A006786). The number of matrices with a(n) ones is given by A191966 and A335820 (up to permutations of rows/columns). - Max Alekseyev, Jan 29 2022

B. Bollobas, Extremal Graph Theory, pp. 309ff.

D. Bienstock E. Gyori, An extremal problem on sparse 0-1 matrices. SIAM J. Discrete Math. 4 (1991), 17-27.

Cf. A006786, A006855, A077269, A191873 A191874, A191966, A300756, A335820, A352472.

a(n) = 2 * A006855(n). - Max Alekseyev, Jan 29 2022

a(11)-a(40) computed from A006855 by Max Alekseyev, Jan 28 2022; Apr 02 2022; Mar 14 2023

A191966 Number of n X n symmetric (0,1) matrices that achieve the record mentioned in A191965.

Original entry on oeis.org

1, 1, 1, 12, 15, 900, 6615, 90720, 1995840, 1360800, 197920800, 359251200, 1297296000, 7264857600, 119870150400, 2615348736000, 29640619008000, 533531142144000, 101370917007360000, 101370917007360000, 425757851430912000, 3325168819675422720000

Offset: 1

R. H. Hardin and N. J. A. Sloane, Jun 18 2011

nonn

Number of labeled squarefree graphs on n nodes with A006855(n) edges. - Max Alekseyev, Jan 29 2022

Max Alekseyev, Table of n, a(n) for n = 1..37

Labeled version of A335820. Rightmost values in A352472.

Cf. A006786, A006855, A077269, A191965, A300756.

a191966 = lambda n: sum( factorial(n) // g.automorphism_group(return_group=False, order=True) for g in graphs.nauty_geng(options=f'-c -f {n} {oeis(6855)(n)}:0') ) # Max Alekseyev, Jan 29 2022

a(11)-a(21) from Max Alekseyev, Jan 29 2022

Corrected and extended to a(37) by Max Alekseyev, Mar 12 2023

A335820 Number of squarefree graphs on n nodes with maximal number of edges.

Original entry on oeis.org

1, 1, 1, 1, 1, 4, 5, 5, 10, 2, 11, 3, 2, 1, 2, 2, 1, 1, 5, 1, 1, 13, 1, 20, 9, 8, 7, 1, 2, 1, 1, 9, 18, 1, 1, 5, 11

Offset: 1

Jason Zimba, Jul 22 2020

Number of squarefree graphs on n nodes with A006855(n) edges.

			There are 2 squarefree graphs on 10 nodes that have maximal number of edges.

C. R. J. Clapham, A. Flockhart, and J. Sheehan, Graphs without Four-Cycles, Journal of Graph Theory, 31 (1989), 29-47.
D. B. West, A. Bialostocki, and J. Schonheim, E3387 (Large Graphs with No 4-cycle), The American Mathematical Monthly, 98 (Aug. - Sep. 1991), 653-655.

Unlabeled version of A191966.

Cf. A006786, A006855, A077269, A300756.

a(22)-a(37) from Brendan McKay, Mar 08 2022

cp's OEIS Frontend

A006786 Number of squarefree graphs on n vertices.

Views

Author

Keywords

References

Links

Crossrefs

Extensions

A191965 A problem of Zarankiewicz: maximal number of 1's in a symmetric n X n matrix of 0's and 1's with 0's on the main diagonal and no "rectangle" with 1's at the four corners.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A191966 Number of n X n symmetric (0,1) matrices that achieve the record mentioned in A191965.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Sage

Extensions

A335820 Number of squarefree graphs on n nodes with maximal number of edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions