A006791 -id:A006791 - cp's OEIS frontend

A000791 Ramsey numbers R(3,n).

1, 3, 6, 9, 14, 18, 23, 28, 36

Offset: 1

a(10) is either 40, 41, or 42 (Goedgebeur, Radziszowski). - Ray G. Opao, Oct 07 2015
Kim proves that a(n) ~ n^2/log n; the lower and upper constants, respectively, can be chosen arbitrarily close to 1/162 and 1. (Kim notes that he made no attempt to make 1/162 tight.) - Charles R Greathouse IV, Jun 23 2023
As of 31 December 2023, Vigleik Angeltveit claims to have ruled out a(10)=42 with a massive computer search. See links. That would mean that 40 <= a(10) <= 41. - Allan C. Wechsler, Apr 05 2024

G. Berman and K. D. Fryer, Introduction to Combinatorics. Academic Press, NY, 1972, p. 175.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 288.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 840.
Brendan McKay, personal communication.
H. J. Ryser, Combinatorial Mathematics. Mathematical Association of America, Carus Mathematical Monograph 14, 1963, p. 42.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vigleik Angeltveit, R(3,10) <= 41, arXiv:2401.00392 [math.CO], 2023.
Thomas Bloom, Problem 165, Problem 544, Problem 553, and Problem 986, Erdős Problems.
Geoff Exoo, Ramsey Numbers
Robert Getschmann, Enumeration of Small Ramsey Graphs (Wayback Machine archive)
Jan Goedgebeur and Stanisław P. Radziszowski, New Computational Upper Bounds for Ramsey Numbers R(3,k), arXiv:1210.5826 [math.CO], 2012-2013.
R. E. Greenwood and A. M. Gleason, Combinatorial relations and chromatic graphs, Canad. J. Math., 7 (1955), 1-7.
J. G. Kalbfleisch, Construction of special edge-chromatic graphs, Canad. Math. Bull., 8 (1965), 575-584.
Jeong Han Kim, The Ramsey number R(3, t) has order of magnitude t^2/log t, Random Structures & Algorithms Vol. 7, No. 3 (1995), pp. 173-207.
Richard L. Kramer, Ricardo's Ramsey Number Page (Wayback Machine archive)
Imre Leader, Friends and Strangers
Math Reference Project, Ramsey Numbers
Mathematical Database, Ramsey's Theory
Brendan McKay, Email to N. J. A. Sloane, Jul. 1991
Online Dictionary of Combinatorics, Ramsey's Theorem (Wayback Machine archive)
Ivars Peterson, Math Trek, Party Games, Science News Online, Vol. 156, No. 23, Dec 04 1999.
Ivars Peterson, Math Trek, Party Games, Dec 06 1999.
Stanisław Radziszowski, Small Ramsey Numbers, The Electronic Journal of Combinatorics, Dynamic Surveys, #DS1: Jan 12, 2014.
Terence Tao, Erdős problem database, see no. 165, 544, 553, 986.
Eric Weisstein's World of Mathematics, Ramsey Number
Wikipedia, Ramsey's Theorem.
Jin Xu and C. K. Wong, Self-complementary graphs and Ramsey numbers I, Discrete Math., 223 (2000), 309-326.

A row of the table in A059442. Cf. A120414.

a(1) = 1 added by N. J. A. Sloane, Nov 05 2023

A006792 Number of n-node vertex-transitive graphs which are not Cayley graphs.

Original entry on oeis.org

2, 0, 0, 0, 0, 4, 8, 0, 4, 0, 82, 0, 0, 0, 112, 0, 132, 0, 66, 0, 1124, 0, 18170, 0, 920, 6, 4162, 0, 0, 0, 48266, 0, 242, 0, 96, 294, 0, 0

Offset: 10

N. J. A. Sloane

McKay, Brendan D.; Royle, Gordon F.; The transitive graphs with at most 26 vertices. Ars Combin. 30 (1990), 161-176.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

B. McKay, Email to N. J. A. Sloane, Jul. 1991
Brendan D. McKay, Cheryl E. Praeger, Vertex-transitive graphs which are not Cayley graphs, I. J. Austral. Math. Soc. Ser. A 56 (1994), no. 1, 53-63.
G. Royle, Transitive graphs
Steven Skiena, A Database of Graphs in Combinatorica Format.
Eric Weisstein's World of Mathematics, Noncayley Graph

Cf. A006799, A185959.

a(n) = A006799(n) - A185959(n). - Andrew Howroyd, Nov 27 2018

More terms from Vladeta Jovovic, Jun 30 2007
a(32)-a(47) from Andrew Howroyd, Nov 27 2018
Duplicate a(32) removed by Andrew Howroyd, Sep 05 2019

A111358 Numbers of planar triangulations with minimum degree 5 and without separating 3- or 4-cycles - that is 3- or 4-cycles where the interior and exterior contain at least one vertex.

Original entry on oeis.org

1, 0, 1, 1, 3, 4, 12, 23, 71, 187, 627, 1970, 6833, 23384, 82625, 292164, 1045329, 3750277, 13532724, 48977625, 177919099, 648145255, 2368046117, 8674199554, 31854078139, 117252592450, 432576302286, 1599320144703, 5925181102878

Offset: 12

Gunnar Brinkmann, Nov 07 2005

nonn

A006791 and this sequence are the same sequence. The correspondence is just that these objects are planar duals of each other. But the offset and step are different: if the cubic graph has 2*n vertices, the dual triangulation has n+2 vertices. - Brendan McKay, May 24 2017

Also the number of 5-connected triangulations on n vertices. - Manfred Scheucher, Mar 17 2023

			The icosahedron is the smallest triangulation with minimum degree 5 and it doesn't contain any separating 3- or 4-cycles. Examples can easily be seen as 2D and 3D pictures using the program CaGe cited above.

G. Brinkmann, CaGe.
Gunnar Brinkmann and Brendan McKay, plantri and fullgen programs for generation of certain types of planar graph.
Gunnar Brinkmann and Brendan McKay, plantri and fullgen programs for generation of certain types of planar graph. [Cached copy, pdf file only, no active links, with permission]
G. Brinkmann and Brendan D. McKay, Construction of planar triangulations with minimum degree 5 , Disc. Math. vol 301, iss. 2-3 (2005) 147-163.
D. A. Holton and B. D. McKay, The smallest non-hamiltonian 3-connected cubic planar graphs have 38 vertices, J. Combinat. Theory B vol 45, iss. 3 (1988) 305-319.
D. A. Holton and B. D. McKay, Erratum, J. Combinat. Theory B vol 47, iss. 2 (1989) 248.

Cf. A081621, A007894, A006791, A000109, A007021, A361578.

A006793 Orders of vertex-transitive graphs which are not Cayley graphs.

Original entry on oeis.org

10, 12, 15, 16, 18, 20, 24, 26, 28, 30, 32, 34, 35, 36, 40, 42, 44, 45, 48, 50, 52, 54, 56, 57, 58, 60, 63, 64

Offset: 1

N. J. A. Sloane

nonn

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

Brendan McKay, Email to N. J. A. Sloane, Jul. 1991
Brendan D. McKay, Cheryl E. Praeger, Vertex-transitive graphs which are not Cayley graphs, I. J. Austral. Math. Soc. Ser. A 56 (1994), no. 1, 53-63.

cp's OEIS Frontend

A000791 Ramsey numbers R(3,n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A006792 Number of n-node vertex-transitive graphs which are not Cayley graphs.

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

A111358 Numbers of planar triangulations with minimum degree 5 and without separating 3- or 4-cycles - that is 3- or 4-cycles where the interior and exterior contain at least one vertex.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A006793 Orders of vertex-transitive graphs which are not Cayley graphs.

Views

Author

Keywords

References

Links