A006785 -id:A006785 - 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

A006787 Number of n-node graphs with no cycles of length less than 5.

Original entry on oeis.org

1, 2, 3, 6, 11, 23, 48, 114, 293, 869, 2963, 12066, 58933, 347498, 2455693, 20592932, 202724920, 2322206466, 30743624324, 468026657815, 8161170076257

Offset: 1

N. J. A. Sloane

Includes graphs with no cycles at all as well as graphs with girth greater than 5.

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
Brendan D. McKay, Isomorph-free exhaustive generation, Table 2.
Brendan D. McKay, Isomorph-Free Exhaustive Generation, J. Algorithms, vol. 26 iss. 2 (1998), 306-324.

Cf. A000066, A000088, A054760, A159847, A126757 (connected, inv. Eul. Transf.), A128236, A128237, A300705.

a(n) = A000088(n) - A128236(n) - A128237(n). - Andrew Howroyd, May 06 2021

Definition corrected by Brendan McKay, Apr 27 2007
a(18)-a(19) (from the McKay reference) added by R. J. Mathar, Jun 17 2008
a(20)-a(21) from Brendan McKay, Mar 11 2018

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

Original entry on oeis.org

0, 1, 3, 15, 59, 296, 1604, 11303, 102108, 1250114, 20738069, 467523871, 14230096759, 581439661069, 31720637440030

Offset: 3

Keith Briggs, May 05 2007

nonn

Cf. A006785, A006787.

Cf. A128041, A128042, A128236-A128243.

a(n) = A006785(n) - A006787(n).

Corrected and extended by Martin Fuller, May 01 2015

A296414 Number of non-isomorphic abstract almost-equidistant graphs on n vertices in R^2. A graph G is abstract almost-equidistant in R^2 if the complement of G does not contain K_3 and G does not contain K_4 nor K_{2,3}.

Original entry on oeis.org

1, 2, 3, 6, 7, 9, 2, 1, 0

Offset: 1

Manfred Scheucher, Dec 11 2017

A set of points in R^d is called almost equidistant if for any three points, some two are at unit distance.

Martin Balko, Attila Pór, Manfred Scheucher, Konrad Swanepoel, and Pavel Valtr, Almost-equidistant sets, arXiv:1706.06375 [math.MG], 2017.
Martin Balko, Attila Pór, Manfred Scheucher, Konrad Swanepoel, and Pavel Valtr, Almost-equidistant sets [supplemental data], 2017.

Cf. A296415, A296416, A296417, A296418, A296419, A006785.

A296415 Number of non-isomorphic abstract almost-equidistant graphs on n vertices in R^3. A graph G is abstract almost-equidistant in R^3 if the complement of G does not contain K_3 and G does not contain K_5 nor K_{3,3}.

Original entry on oeis.org

1, 2, 3, 7, 13, 29, 50, 69, 35, 7, 1, 0

Offset: 1

Manfred Scheucher, Dec 11 2017

A set of points in R^d is called almost equidistant if for any three points, some two are at unit distance.

Martin Balko, Attila Pór, Manfred Scheucher, Konrad Swanepoel, and Pavel Valtr, Almost-equidistant sets, arXiv:1706.06375 [math.MG], 2017.
Martin Balko, Attila Pór, Manfred Scheucher, Konrad Swanepoel, and Pavel Valtr, Almost-equidistant sets [supplemental data], 2017.

Cf. A296414, A296416, A296417, A296418, A006785.

A296416 Number of non-isomorphic abstract almost-equidistant graphs on n vertices in R^4. A graph G is abstract almost-equidistant in R^4 if the complement of G does not contain K_3 and G does not contain K_6 nor K_{1,3,3}.

Original entry on oeis.org

1, 2, 3, 7, 14, 37, 97, 316, 934, 2362, 2814, 944, 59, 4, 1, 1, 0

Offset: 1

Manfred Scheucher, Dec 11 2017

A set of points in R^d is called almost equidistant if for any three points, some two are at unit distance.

Martin Balko, Attila Pór, Manfred Scheucher, Konrad Swanepoel, and Pavel Valtr, Almost-equidistant sets, arXiv:1706.06375 [math.MG], 2017.
Martin Balko, Attila Pór, Manfred Scheucher, Konrad Swanepoel, and Pavel Valtr, Almost-equidistant sets [supplemental data], 2017.

Cf. A296414, A296415, A296417, A296418, A006785.

A296417 Number of non-isomorphic abstract almost-equidistant graphs on n vertices in R^5. A graph G is abstract almost-equidistant in R^5 if the complement of G does not contain K_3 and G does not contain K_7 nor K_{3,3,3}.

Original entry on oeis.org

1, 2, 3, 7, 14, 38, 106, 402, 1817, 11132, 86053, 803299, 7623096, 58770989

Offset: 1

Manfred Scheucher, Dec 11 2017

A set of points in R^d is called almost equidistant if for any three points, some two are at unit distance.

Martin Balko, Attila Pór, Manfred Scheucher, Konrad Swanepoel, and Pavel Valtr, Almost-equidistant sets, arXiv:1706.06375 [math.MG], 2017.
Martin Balko, Attila Pór, Manfred Scheucher, Konrad Swanepoel, and Pavel Valtr, Almost-equidistant sets [supplemental data], 2017.

Cf. A296414, A296415, A296416, A296418, A006785.

A296418 Number of non-isomorphic abstract almost-equidistant graphs on n vertices in R^6. A graph G is abstract almost-equidistant in R^6 if the complement of G does not contain K_3 and G does not contain K_8 nor K_{1,3,3,3}.

Original entry on oeis.org

1, 2, 3, 7, 14, 38, 107, 409, 1888, 12064, 103333, 1217849, 19170728

Offset: 1

Manfred Scheucher, Dec 11 2017

A set of points in R^d is called almost equidistant if for any three points, some two are at unit distance.

Martin Balko, Attila Pór, Manfred Scheucher, Konrad Swanepoel, and Pavel Valtr, Almost-equidistant sets, arXiv:1706.06375 [math.MG], 2017.
Martin Balko, Attila Pór, Manfred Scheucher, Konrad Swanepoel, and Pavel Valtr, Almost-equidistant sets [supplemental data], 2017.

Cf. A296414, A296415, A296416, A296417, A006785.

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).

A304124 Number of simple graphs with n vertices which contain no K4 subgraph.

Original entry on oeis.org

1, 2, 4, 10, 29, 120, 685, 6431, 103164, 2894632, 138892304, 11118977705, 1459412127955

Offset: 1

Brendan McKay, May 06 2018

The graphs do not need to be connected.

Cf. A000088, A006785 (no K3), A115196 (graphs by clique number), A304125 (no K5).

a(n) = 1+A052450(n)+A052451(n).

a(13) from Brendan McKay, May 08 2018

cp's OEIS Frontend

A006786 Number of squarefree graphs on n vertices.

Views

Author

Keywords

References

Links

Crossrefs

Extensions

A006787 Number of n-node graphs with no cycles of length less than 5.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Crossrefs

Formula

Extensions

A296414 Number of non-isomorphic abstract almost-equidistant graphs on n vertices in R^2. A graph G is abstract almost-equidistant in R^2 if the complement of G does not contain K_3 and G does not contain K_4 nor K_{2,3}.

Views

Author

Keywords

Comments

Links

Crossrefs

A296415 Number of non-isomorphic abstract almost-equidistant graphs on n vertices in R^3. A graph G is abstract almost-equidistant in R^3 if the complement of G does not contain K_3 and G does not contain K_5 nor K_{3,3}.

Views

Author

Keywords

Comments

Links

Crossrefs

A296416 Number of non-isomorphic abstract almost-equidistant graphs on n vertices in R^4. A graph G is abstract almost-equidistant in R^4 if the complement of G does not contain K_3 and G does not contain K_6 nor K_{1,3,3}.

Views

Author

Keywords

Comments

Links

Crossrefs

A296417 Number of non-isomorphic abstract almost-equidistant graphs on n vertices in R^5. A graph G is abstract almost-equidistant in R^5 if the complement of G does not contain K_3 and G does not contain K_7 nor K_{3,3,3}.

Views

Author

Keywords

Comments

Links

Crossrefs

A296418 Number of non-isomorphic abstract almost-equidistant graphs on n vertices in R^6. A graph G is abstract almost-equidistant in R^6 if the complement of G does not contain K_3 and G does not contain K_8 nor K_{1,3,3,3}.

Views

Author

Keywords

Comments

Links

Crossrefs

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

A304124 Number of simple graphs with n vertices which contain no K4 subgraph.

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions