OFFSET
1,1
COMMENTS
The Ramsey core number rc(s,t) is the smallest n such that for all edge 2-colorings of K_n, either the factor induced by the first color contains an s-core or the second factor contains a t-core. (A k-core is a subgraph with minimum degree at least k.)
The beginning of the square array is:
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
3, 5, 6, 8, 9, 10, 12, 13, 14, 15, 17, ...
4, 6, 8, 10, 11, 13, 14, 15, 17, 18, 19, ...
5, 8, 10, 11, 13, 15, 16, 18, 19, 20, 22, ...
6, 9, 11, 13, 15, 16, 18, 20, 21, 23, 24, ...
7, 10, 13, 15, 16, 18, 20, 21, 23, 25, 26, ...
8, 12, 14, 16, 18, 20, 22, 23, 25, 26, 28, ...
REFERENCES
R. Klein and J. Schönheim, Decomposition of K_{n} into degenerate graphs, In Combinatorics and Graph Theory Hefei 6-27, April 1992. World Scientific. Singapore, New Jersey, London, Hong Kong, 141-1.
LINKS
Paolo Xausa, Table of n, a(n) for n = 1..10000
Allan Bickle, The k-Cores of a Graph, Ph.D. Dissertation, Western Michigan University, 2010.
Allan Bickle, Structural results on maximal k-degenerate graphs, Discuss. Math. Graph Theory 32 4 (2012), 659-676.
Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.
Sascha Stoll, On Subgraphs With Minimum Degree Restrictions, Master’s Thesis, Karlsruhe Institute of Technology, 2019.
FORMULA
a(n) = rc(n,n) = ceiling(2*n - 3/2 + sqrt(2*(n-1)^2 + 9/4)).
EXAMPLE
For order 5, one of the two factors has at least 5 edges, and so contains a cycle. For order 4, K_4 decomposes into two paths. Thus rc(2,2)=5.
MATHEMATICA
A361684[n_]:=Ceiling[2n-3/2+Sqrt[2(n-1)^2+9/4]];
Array[A361684, 100] (* Paolo Xausa, Dec 01 2023 *)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Allan Bickle, Mar 28 2023
STATUS
approved