A024607 -id:A024607 - cp's OEIS frontend

A006785 Number of triangle-free graphs on n vertices.

1, 2, 3, 7, 14, 38, 107, 410, 1897, 12172, 105071, 1262180, 20797002, 467871369, 14232552452, 581460254001, 31720840164950

Offset: 1

N. J. A. Sloane

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

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
CombOS - Combinatorial Object Server, Generate graphs
P. Erdős, D. J. Kleitman, and B. L. Rothschild, Asymptotic enumeration of k_n-free graphs. In Colloquio Internazionale sulle Teorie Combinatorie, (Rome, 1973), Tomo II, Atti dei Convegni Lincei, No. 17, pp. 19-27. Accad. Naz. Lincei, Rome.
Jérôme Kunegis, Jun Sun, and Eiko Yoneki, Guided Graph Generation: Evaluation of Graph Generators in Terms of Network Statistics, and a New Algorithm, arXiv:2303.00635 [cs.SI], 2023, p. 17.
Brendan McKay, Emails to N. J. A. Sloane, 1991
B. D. McKay, Isomorph-free exhaustive generation, J Algorithms, 26 (1998) 306-324.
W. Pu, J. Choi, and E. Amir, Lifted Inference On Transitive Relations, Workshops at the Twenty-Seventh AAAI Conference on Statistical Relational Artificial Intelligence, 2013.
Eric Weisstein's World of Mathematics, Triangle-Free Graph

Cf. A024607.

Row sums of A283417.

Erdős, Kleitman, & Rothschild prove that a(n) = 2^(n^2/4 + o(n^2)) and a(n) = (1 + o(1/n))*A033995(n). - Charles R Greathouse IV, Feb 01 2018

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

2 more terms from Brendan McKay, Jan 12 2013

A372169 Number of unlabeled triangle-free graphs covering n vertices.

Original entry on oeis.org

1, 0, 1, 1, 4, 7, 24, 69, 303, 1487, 10275, 92899, 1157109, 19534822, 447074367, 13764681083, 567227701549, 31139379910949

Offset: 0

Gus Wiseman, Apr 23 2024

The labeled version is A372168.

			Non-isomorphic representatives of the a(5) = 7 graphs:
  12-35-45
  13-24-35-45
  14-25-35-45
  15-25-35-45
  12-13-24-35-45
  15-23-24-35-45
  13-14-23-24-35-45

Eric Weisstein's World of Mathematics, Triangle-Free Graph
Gus Wiseman, The a(6) = 24 unlabeled triangle-free graphs covering 6 vertices.

Dominated by A002494, labeled A006129.
Covering case of A006785, labeled A213434.
The connected case is A024607.
For all cycles (not just triangles) we have A144958, labeled A105784.
The labeled version is A372168.
For a unique triangle (labeled) we have A372171, non-covering A372172.
Column k = 0 of A372173, labeled A372167.
For a unique triangle (unlabeled) we have A372174, non-covering A372194.
A001858 counts acyclic graphs, unlabeled A005195.
A006125 counts simple graphs, unlabeled A000088.
A054548 counts covering graphs by number of edges, unlabeled A370167.
A372170 counts graphs by triangles, unlabeled A263340.
Cf. A000055, A000272, A053530, A121251, A322700, A372175, A372191.

First differences of A006785.

A372168 Number of triangle-free simple labeled graphs covering n vertices.

Original entry on oeis.org

1, 0, 1, 3, 22, 237, 3961, 99900, 3757153, 208571691, 16945953790, 1999844518737, 340422874696873, 83041703920313712, 28850117307732482737, 14191512425207950473867, 9829313296102303971441502

Offset: 0

Gus Wiseman, Apr 23 2024

The unlabeled version is A372169.

			The a(4) = 22 graphs are:
  12-34
  13-24
  14-23
  12-13-14
  12-13-24
  12-13-34
  12-14-23
  12-14-34
  12-23-24
  12-23-34
  12-24-34
  13-14-23
  13-14-24
  13-23-24
  13-23-34
  13-24-34
  14-23-24
  14-23-34
  14-24-34
  12-13-24-34
  12-14-23-34
  13-14-23-24

Eric Weisstein's World of Mathematics, Triangle-Free Graph

Dominated by A006129, unlabeled A002494.
For all cycles (not just triangles) we have A105784, unlabeled A144958.
Covering case of A213434 (column k = 0 of A372170, unlabeled A263340).
The connected case is A345218, unlabeled A024607.
Column k = 0 of A372167, unlabeled A372173.
The unlabeled version is A372169.
For a unique triangle we have A372171, non-covering A372172.
A000088 counts unlabeled graphs, labeled A006125.
A001858 counts acyclic graphs, unlabeled A005195.
A054548 counts covering graphs by number of edges, unlabeled A370167.
Cf. A000272, A053530, A121251, A367862, A367863, A372191, A372174, A372175.

cys[y_]:=Select[Subsets[Union@@y,{3}],MemberQ[y,{#[[1]],#[[2]]}] && MemberQ[y,{#[[1]],#[[3]]}] && MemberQ[y,{#[[2]],#[[3]]}]&];
Table[Length[Select[Subsets[Subsets[Range[n], {2}]],Union@@#==Range[n]&&Length[cys[#]]==0&]],{n,0,5}]

Binomial transform is A213434.

A126744 Triangle read by rows: T(n,k) gives number of connected graphs on n nodes with clique number n-k, (n>=2, k=0..n-2).

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 1, 3, 11, 6, 1, 4, 25, 63, 19, 1, 5, 45, 266, 477, 59, 1, 6, 73, 785, 4646, 5339, 267, 1, 7, 109, 1908, 26205, 136935, 94535, 1380, 1, 8, 155, 4085, 110140, 1696407, 7121703, 2774240, 9832, 1, 9, 211, 7992, 384209, 13779220, 209046708, 647596643, 135794730, 90842

Offset: 2

N. J. A. Sloane, Feb 18 2007

This sequence can be derived from A263341 since the number of graphs with clique number <= k is the Euler transform of the number of connected graphs with clique number <= k. - Andrew Howroyd, Feb 19 2020

			Triangle begins:
n=...1...2...3...4....5....6.....7......8........9........10
k.------------------------------------------------------------
2|...0...1...1...3....6...19....59....267.....1380......9832 = A024607
3|...0...0...1...2...11...63...477...5339....94535...2774240 = A126745
4|...0...0...0...1....3...25...266...4646...136935...7121703 = A126746
5|...0...0...0...0....1....4....45....785....26205...1696407 = A126747
6|...0...0...0...0....0....1.....5.....73.....1908....110140 = A126748
7|...0...0...0...0....0....0.....1......6......109......4085 = A217987
8|...0...0...0...0....0....0.....0......1........7.......155
  ...
From _Andrew Howroyd_, Feb 19 2020: (Start)
As a triangle with columns being clique number >= 2:
     1;
     1,       1;
     3,       2,       1;
     6,      11,       3,       1;
    19,      63,      25,       4,      1;
    59,     477,     266,      45,      5,    1;
   267,    5339,    4646,     785,     73,    6,   1;
  1380,   94535,  136935,   26205,   1908,  109,   7, 1;
  9832, 2774240, 7121703, 1696407, 110140, 4085, 155, 8, 1;
  ...
(End)

Andrew Howroyd, Table of n, a(n) for n = 2..79 (rows 2..13 derived from Brendan McKay data in A263341)
Keith M. Briggs, Combinatorial Graph Theory

Diagonals give A024607, A126745, A126746, A126747, A126748, A217987.
Row sums are A001349.
Cf. A263341.

Terms a(47) and beyond derived from A263341 added by Andrew Howroyd, Feb 19 2020

A128240 Number of n-node (unlabeled) connected graphs with girth 3.

Original entry on oeis.org

0, 0, 1, 3, 15, 93, 794, 10850, 259700, 11706739, 1006609723, 164058686415, 50335888444167, 29003487017067011, 31397381129017616776, 63969560112658419275907, 245871831682052901418048916

Offset: 1

Keith Briggs, May 05 2007

nonn

Number of unlabeled, connected graphs on n vertices with at least one induced subgraph isomorphic to a K_3, where K_3 is the complete graph on three vertices (a triangle). - Travis Hoppe and Anna Petrone, Jun 01 2014

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, Triangle-Free Graph

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

Cf. A128041, A128042, A128236-A128243.

Corrected and extended by Martin Fuller, May 01 2015

Information added by Falk Hüffner, Nov 27 2015

A128241 Number of n-node (unlabeled) connected graphs with girth 4.

Original entry on oeis.org

0, 1, 2, 11, 41, 220, 1243, 9368, 89049, 1135894, 19381407, 445505570, 13741579905, 566739127723, 31124921885829

Offset: 3

Keith Briggs, May 05 2007

Cf. A024607, A126757.

Cf. A128041, A128042, A128236-A128243.

a(n) = A024607(n) - A126757(n). - Martin Fuller, May 01 2015

Corrected and extended by Martin Fuller, May 01 2015

A283417 Number T(n,k) of triangle-free graphs on n unlabeled nodes with exactly k connected components; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 3, 2, 1, 1, 0, 6, 4, 2, 1, 1, 0, 19, 10, 5, 2, 1, 1, 0, 59, 28, 11, 5, 2, 1, 1, 0, 267, 90, 32, 12, 5, 2, 1, 1, 0, 1380, 363, 100, 33, 12, 5, 2, 1, 1, 0, 9832, 1784, 397, 104, 34, 12, 5, 2, 1, 1, 0, 90842, 11770, 1892, 407, 105, 34, 12, 5, 2, 1, 1

Offset: 0

Alois P. Heinz, Apr 14 2017

			Triangle T(n,k) begins:
  1;
  0,    1;
  0,    1,    1;
  0,    1,    1,   1;
  0,    3,    2,   1,   1;
  0,    6,    4,   2,   1,  1;
  0,   19,   10,   5,   2,  1,  1;
  0,   59,   28,  11,   5,  2,  1, 1;
  0,  267,   90,  32,  12,  5,  2, 1, 1;
  0, 1380,  363, 100,  33, 12,  5, 2, 1, 1;
  0, 9832, 1784, 397, 104, 34, 12, 5, 2, 1, 1;
  ...

Alois P. Heinz, Rows n = 0..17, flattened
Index entries for triangles generated by the Multiset Transformation

Columns k=0-1 give: A000007, A024607.

Row sums give A006785.

G.f.: Product_{j>=1} 1/(1-y*x^j)^A024607(j).

A345218 Number of labeled triangle-free connected simple graphs on n vertices.

Original entry on oeis.org

1, 1, 3, 19, 207, 3571, 93243, 3603139, 203658087, 16725737971, 1985745828483, 339119822487139, 82867477502576847, 28816562818537878931, 14182270437347915240523, 9825699599254424454332419

Offset: 1

Brendan McKay, Jun 11 2021

LOG transform of A213434.

Labeled version of A024607.

Cf. A024607, A213434.

A165452 Number of connected graphs of odd girth at least 7 with n vertices.

Original entry on oeis.org

1, 1, 1, 3, 5, 17, 45, 184, 748, 4143, 26532, 221032, 2326853, 32202266, 589436301, 14459238676, 477812658943

Offset: 1

Friedrich Regen (friedrich.regen(AT)tu-ilmenau.de), Sep 20 2009

nonn

The odd girth of a graph is the length of a shortest cycle of odd length. Thus, these are the connected graphs that do not have a triangle or C_5 as induced subgraph. - Falk Hüffner, Jan 15 2016

The bipartite graphs (which have no odd cycles) are included.

F. Hüffner, tinygraph, software for generating integer sequences based on graph properties, version ece94ef.

Cf. A005142, A024607.

Inverse EULER transform of A345247.

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

a(17) added by Brendan McKay, Jun 12 2021

A243332 Number of simple connected graphs with n nodes that are integral and triangle-free.

Original entry on oeis.org

1, 1, 0, 1, 1, 3, 1, 3, 0, 14, 8, 18, 33, 75

Offset: 1

Travis Hoppe and Anna Petrone, Jun 03 2014

Travis Hoppe and Anna Petrone, Encyclopedia of Finite Graphs.
Travis Hoppe and Anna Petrone, Integer sequence discovery from small graphs, arXiv:1408.3644 [math.CO], 2014.

Cf. A064731 (integral graphs), A024607 (triangle-free graphs).

a243332 = lambda n: sum(1 for g in graphs.nauty_geng(f'-c -t {n}') if sum(m for ,m in g.charpoly().roots(ZZ))==n) # _Max Alekseyev, Jan 31 2024

a(11)-a(14) from Max Alekseyev, Feb 02 2024

cp's OEIS Frontend

A006785 Number of triangle-free graphs on n vertices.

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

A372169 Number of unlabeled triangle-free graphs covering n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A372168 Number of triangle-free simple labeled graphs covering n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A126744 Triangle read by rows: T(n,k) gives number of connected graphs on n nodes with clique number n-k, (n>=2, k=0..n-2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A128240 Number of n-node (unlabeled) connected graphs with girth 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A128241 Number of n-node (unlabeled) connected graphs with girth 4.

Views

Author

Keywords

Crossrefs

Formula

Extensions

A283417 Number T(n,k) of triangle-free graphs on n unlabeled nodes with exactly k connected components; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A345218 Number of labeled triangle-free connected simple graphs on n vertices.

Views

Author

Keywords

Comments

Crossrefs

A165452 Number of connected graphs of odd girth at least 7 with n vertices.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A243332 Number of simple connected graphs with n nodes that are integral and triangle-free.

Views

Author

Keywords