A006786 -id:A006786 - cp's OEIS frontend

A077269 Number of connected squarefree graphs on n nodes.

1, 1, 2, 3, 8, 19, 57, 186, 740, 3389, 18502, 120221, 932260, 8596844, 93762704, 1201732437, 17992683043, 313098431306, 6305419392541

Offset: 1

Eric W. Weisstein, Nov 01 2002

From R. J. Mathar, Apr 04 2022 (Start)
The sequence contains the row sums of the number of connected squarefree graphs on V vertices with E edges, the triangle with V>=0, E>=0:
;
;
1;
0  1  1;
0  0  2  1;
0  0  0  3  4  1;
0  0  0  0  6  9  4;
0  0  0  0  0 11 24  17   5;
0  0  0  0  0  0 23  61  66  31   5;
0  0  0  0  0  0  0  47 169 248 192  74 10;
(End)

Felix Arends, Joel Ouaknine, and Charles W. Wampler, On Searching for Small Kochen-Specker Vector Systems (extended version), arXiv:1111.3301 [quant-ph], 2011.
CombOS - Combinatorial Object Server, Generate graphs
R. J. Mathar, Illustrations
Eric Weisstein's World of Mathematics, Square-Free Graph
Index entries for sequences of squarefree graphs

Cf. A006786, A243243 (complement).

A006786 = {1, 2, 4, 8, 18, 44, 117, 351, 1230, 5069, 25181, 152045, 1116403, 9899865, 104980369, 1318017549, 19427531763, 333964672216, 6660282066936};
mob[m_, n_] := If[Mod[m, n] == 0, MoebiusMu[m/n], 0];
EULERi[b_] := Module[{a, c, i, d}, c = {}; For[i = 1, i <= Length[b], i++, c = Append[c, i*b[[i]] - Sum[c[[d]]*b[[i - d]], {d, 1, i - 1}]]]; a = {}; For[i = 1, i <= Length[b], i++, a = Append[a, (1/i)*Sum[mob[i, d]*c[[d]], {d, 1, i}]]]; Return[a]];
EULERi[A006786] (* Jean-François Alcover, Aug 18 2018, after Andrew Howroyd *)

Inverse Euler transform of A006786. - Andrew Howroyd, Nov 03 2017

More terms from Jim Nastos, Aug 27 2004
4 more terms from Vladeta Jovovic, May 17 2008
a(18)-a(19) using Brendan McKay's extension to A006786 by Alois P. Heinz, 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

A300756 Triangle T(n,k) read by rows: number of squarefree graphs on n nodes with k components.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 2, 1, 1, 0, 3, 3, 1, 1, 0, 8, 5, 3, 1, 1, 0, 19, 14, 6, 3, 1, 1, 0, 57, 33, 16, 6, 3, 1, 1, 0, 186, 98, 39, 17, 6, 3, 1, 1, 0, 740, 305, 116, 41, 17, 6, 3, 1, 1, 0, 3389, 1133, 355, 122, 42, 17, 6, 3, 1, 1, 0, 18502, 4824, 1288, 373, 124, 42, 17, 6, 3, 1, 1, 0, 120221, 24575, 5332, 1343

Offset: 0

R. J. Mathar, Mar 12 2018

Multiset transform of A077269.

			The triangle starts in row n=0 with columnes 0<=k<=n as
1
0 1
0 1 1
0 2 1 1
0 3 3 1 1
0 8 5 3 1 1
0 19 14 6 3 1 1
0 57 33 16 6 3 1 1
0 186 98 39 17 6 3 1 1
0 740 305 116 41 17 6 3 1 1
0 3389 1133 355 122 42 17 6 3 1 1
0 18502 4824 1288 373 124 42 17 6 3 1 1
0 120221 24575 5332 1343 379 125 42 17 6 3 1 1
0 932260 150292 26415 5499 1361 381 125 42 17 6 3 1 1
0 8596844 1110759 157791 26973 5554 1367 382 125 42 17 6 3 1 1
0 93762704 9876826 1146376 159799 27146 5572 1369 382 125 42 17 6 3 1 1
0 1201732437 104856709 10078812 1154493 160372 27201 5578 1370 382 125 42 17 6 3 1 1
0 17992683043 1317129728 106250470 10116666 1156565 160545 27219 5580 1370 382 125 42 17 6 3 1 1

Max Alekseyev, Table of n, a(n) for n = 0..209
Index entries for sequences of squarefree graphs

Cf. A077269 (column k=1), A006786 (row sums).

G. f.: Sum_{n >= k >= 0} T(n,k)*x^n*y^k = exp( Sum_{m>=1} F(x^m)*y^m/m ), where F(y) is the generating function for A077269. - Max Alekseyev, Mar 30 2022

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

A345249 Number of labeled simple graphs on n vertices without cycles of length 4.

Original entry on oeis.org

1, 2, 8, 54, 548, 7984, 163440, 4599908, 174204728, 8721120744, 568964631296, 47787888342520, 5112015062311008, 689824902243337856, 116423739687724785152, 24387469030487505651984, 6296486009090647137387200, 1991072810881504185092485408

Offset: 1

Brendan McKay, Jun 12 2021

Index entries for sequences of squarefree graphs

EXP transform of A345248. Row sums of A352472.
A006786 counts isomorphism classes.
Cf. A213434, A352258 (loops allowed).

A039751 Number of n-node graphs containing a 4-cycle.

Original entry on oeis.org

0, 0, 0, 0, 3, 16, 112, 927, 11995, 273438, 12000099, 1018972683, 165091020547, 50502030251549, 29054155647335623, 31426485969699328399, 64001015704526239877379, 245935864153532913256188013, 1787577725145611700213913518632, 24637809253125004524376347209365832

Offset: 0

N. J. A. Sloane

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 228.

A000088 = Cases[Import["https://oeis.org/A000088/b000088.txt", "Table"], {, }][[All, 2]];
A006786 = Cases[Import["https://oeis.org/A006786/b006786.txt", "Table"], {, }][[All, 2]];
a[n_] := If[n < 2, 0, A000088[[n + 1]] - A006786[[n]]];
a /@ Range[0, 19] (* Jean-François Alcover, Nov 10 2019 *)

a(n) = A000088(n) - A006786(n). - Falk Hüffner, Nov 27 2015

Using formula, a(0) and a(6) corrected and more terms added by Falk Hüffner, Nov 27 2015

a(18)-a(19) from A000088 and A006786 by Jean-François Alcover, Nov 10 2019

A138347 Number of squarefree bipartite graphs on n vertices.

Original entry on oeis.org

1, 2, 3, 6, 10, 21, 39, 86, 182, 440, 1074, 2941, 8424, 26720, 90883, 340253, 1384567, 6186907, 30219769, 161763233, 946742190, 6054606722, 42229136988, 320741332093, 2648348712904

Offset: 1

Vladeta Jovovic, May 18 2008

nonn

CombOS - Combinatorial Object Server, Generate graphs
B. D. McKay, Isomorph-free exhaustive generation, J Algorithms, 26 (1998) 306-324.

Cf. A006786, A300749.

More terms from Brendan McKay, Feb 04 2013

One more term from Brendan McKay, Mar 11 2018

A243243 Number of unlabeled, connected graphs on n vertices with at least one subgraph isomorphic to a C_4, where C_4 is the cycle graph on four vertices.

Original entry on oeis.org

0, 0, 0, 3, 13, 93, 796, 10931, 260340, 11713182, 1006682063, 164059710255, 50335906936959, 29003487454251217, 31397381142667479256, 63969560113223974443840, 245871831682084008526845525, 1787331725248899088577102145274, 24636021429399867655316345340289103

Offset: 1

Travis Hoppe and Anna Petrone, Jun 01 2014

nonn

Travis Hoppe and Anna Petrone, Encyclopedia of Finite Graphs
T. Hoppe and A. Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644 [math.CO], 2014.
Eric Weisstein's World of Mathematics, Square-Free Graph

Cf. A001349, A077269.

terms = 19;
mob[m_, n_] := If[Mod[m, n] == 0, MoebiusMu[m/n], 0];
EULERi[b_] := Module[{a, c, i, d}, c = {}; For[i = 1, i <= Length[b], i++, c = Append[c, i*b[[i]] - Sum[c[[d]]*b[[i - d]], {d, 1, i - 1}]]]; a = {}; For[i = 1, i <= Length[b], i++, a = Append[a, (1/i)*Sum[mob[i, d]*c[[d]], {d, 1, i}]]]; Return[a]];
permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
a88[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!];
A001349 = EULERi[Array[a88, terms]];
A006786 = {1, 2, 4, 8, 18, 44, 117, 351, 1230, 5069, 25181, 152045, 1116403, 9899865, 104980369, 1318017549, 19427531763, 333964672216, 6660282066936};
A077269 = EULERi[A006786];
A001349 - A077269 (* Jean-François Alcover, Feb 15 2019, after Andrew Howroyd in A001349 and A077269 *)

a(n) = A001349(n) - A077269(n).

a(11)-a(17) using formula from Falk Hüffner, Jan 15 2016

a(18)-a(19) from Jean-François Alcover, Feb 15 2019 using Andrew Howroyd's code.

cp's OEIS Frontend

A077269 Number of connected squarefree graphs on n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

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

A300756 Triangle T(n,k) read by rows: number of squarefree graphs on n nodes with k components.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A345249 Number of labeled simple graphs on n vertices without cycles of length 4.

Views

Author

Keywords

Links

Crossrefs

A039751 Number of n-node graphs containing a 4-cycle.

Views

Author

Keywords

References

Programs

Mathematica

Formula

Extensions

A138347 Number of squarefree bipartite graphs on n vertices.

Views

Author

Keywords

Links

Crossrefs

Extensions

A243243 Number of unlabeled, connected graphs on n vertices with at least one subgraph isomorphic to a C_4, where C_4 is the cycle graph on four vertices.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica