A077269 -id:A077269 - cp's OEIS frontend

A242790 Number of connected diamond-free graphs on n nodes.

1, 1, 2, 4, 11, 39, 165, 967, 7684, 87012, 1410465, 32640019

Offset: 1

Travis Hoppe and Anna Petrone, May 22 2014

An equivalent definition: Number of simple connected graphs with n nodes that are have no subgraph isomorphic to the diamond graph or the complete graph K_4. This is the same because a graph contains a diamond as a subgraph iff it contains a diamond or K_4 as induced subgraph. - Falk Hüffner, Jan 11 2015

Travis Hoppe and Anna Petrone, Encyclopedia of Finite Graphs
Falk Hüffner, tinygraph, software for generating integer sequences based on graph properties, version ece94ef.
Eric Weisstein's World of Mathematics, Diamond Graph

Cf. A077269 (connected squarefree graphs).

Cf. also A242790 (diamond free graphs), A079574 (K_4 free graphs).

Entry revised by N. J. A. Sloane, Jan 11 2016

a(11) and a(12) added using tinygraph by Falk Hüffner, Jan 15 2016

A006786 Number of squarefree graphs on n vertices.

Original entry on oeis.org

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

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

A352472 Triangle T(n,k) read by rows: the number of traceless symmetric binary n X n matrices with 2k one's and no all-1 2 X 2 submatrix.

Original entry on oeis.org

1, 1, 1, 1, 3, 3, 1, 1, 6, 15, 20, 12, 1, 10, 45, 120, 195, 162, 15, 1, 15, 105, 455, 1320, 2508, 2680, 900, 1, 21, 210, 1330, 5880, 18564, 40474, 54750, 35595, 6615, 1, 28, 378, 3276, 20265, 93240, 320040, 795120, 1333080, 1323840, 619920, 90720, 1, 36, 630, 7140, 58527, 364896

Offset: 1

R. J. Mathar, Mar 17 2022

Symmetry and traceless mean that the number of 1's is always even; the corresponding zeros for odd numbers are not shown here.

			The triangle starts at 1 X 1 matrices and 0,2,4,... ones as
1: 1;
2: 1  1;
3: 1  3   3    1;
4: 1  6  15   20    12;
5: 1 10  45  120   195    162      15;
6: 1 15 105  455  1320   2508    2680     900;
7: 1 21 210 1330  5880  18564   40474   54750    35595     6615;
8: 1 28 378 3276 20265  93240  320040  795120  1333080  1323840   619920    90720;
9: 1 36 630 7140 58527 364896 1763076 6578640 18514935 37535932 50808870 40684140 15892065 1995840;

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

Cf. A350189 (allows nonzero trace), A345249 (row sums), A006855 (row lengths minus 1), A191966 (rightmost values).

T(n,1) = A000217(n-1). - R. J. Mathar, Mar 25 2022
T(n,2) = 3*A000332(n+1). T(n,3) = A093566(n+1). - Conjectured by R. J. Mathar, Mar 25 2022; proved by Max Alekseyev, Apr 02 2022
G.f.: F(x,y) = Sum_{n,k} T(n,k)*(x^n/n!)*y^k = exp( Sum_G x^n(G) * y^e(G) / |Aut(G)| ), where G runs over the connected squarefree graphs (cf. A077269), n(G) and e(G) are the numbers of nodes and edges in G, and Aut(G) is the automorphism group of G. It follows that F(x,y) = exp(x) * (1 + (1/2)*x^2*y + ((1/2)*x^3 + (1/8)*x^4)*y^2 + ((1/6)*x^3 + (2/3)*x^4 + (1/4)*x^5 + (1/48)*x^6)*y^3 + O(y^4)), implying the above formulas for T(n,2) and T(n,3). - Max Alekseyev, Apr 02 2022

A241784 Number of simple connected graphs on n nodes with no cycle of length 5.

Original entry on oeis.org

1, 1, 2, 6, 13, 44, 144, 577, 2457, 12499, 72394, 508942, 4408389, 49858593, 769196039, 16729819397

Offset: 1

Travis Hoppe and Anna Petrone, Apr 28 2014

Inverse EULER transformation of A345216 (not necessarily connected)

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.
F. Hüffner, tinygraph, software for generating integer sequences based on graph properties, version 29e68fa.
Eric Weisstein's World of Mathematics, Cycle Graph

Cf. Squarefree (C_4) graphs A077269.

a(11)-a(14) added using tinygraph by Falk Hüffner, Sep 22 2020

a(15) and a(16) added by Brendan McKay, Jun 10 2021

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

Original entry on oeis.org

1, 1, 4, 28, 302, 4776, 106732, 3249352, 131290812, 6922560160, 470586936176, 40833342324864, 4482709905772936, 617622136930640128, 106013904370382120400, 22516967955697072408576, 5880701545642715236590608, 1877504184190590494772860928

Offset: 1

Brendan McKay, Jun 12 2021

From R. J. Mathar, Apr 03 2022 (Start)
The sequence contains the row sums of the number of labeled connected simple graphs on V vertices with E edges, the triangle with V>=0, E>=0:
;
;
1;
0  3  1;
0  0 16  12;
0  0  0 125  162    15;
0  0  0   0 1296  2580   900;
0  0  0   0    0 16807  47715   35595     6615 ;
0  0  0   0    0     0 262144 1006488  1270080   619920    90720;
0  0  0   0    0     0      0 4782969 23859108 44893170 39867660  15892065  1995840 ;
(End)

LOG transform of A345249.
A077269 counts isomorphism classes.
Cf. A345218.

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

A242790 Number of connected diamond-free graphs on n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

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

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

A352472 Triangle T(n,k) read by rows: the number of traceless symmetric binary n X n matrices with 2k one's and no all-1 2 X 2 submatrix.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A241784 Number of simple connected graphs on n nodes with no cycle of length 5.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Crossrefs

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