|
%I #45 May 04 2024 07:05:41
%S 2,3,3,4,5,4,5,6,6,5,6,8,8,8,6,7,9,10,10,9,7,8,10,11,11,11,10,8,9,12,
%T 13,13,13,13,12,9,10,13,14,15,15,15,14,13,10,11,14,15,16,16,16,16,15,
%U 14,11,12,15,17,18,18,18,18,18,17,15,12,13,17,18,19,20,20,20,20,19,18,17,13
%N Array of Ramsey core number rc(s,t) read by antidiagonals.
%C 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.)
%D 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-155.
%H Allan Bickle, <a href="https://allanbickle.files.wordpress.com/2016/05/dissertation4.pdf">The k-Cores of a Graph</a>, Ph.D. Dissertation, Western Michigan University, 2010.
%H Allan Bickle, <a href="https://www.dmgt.uz.zgora.pl/publish/pdf.php?doi=1637">Structural results on maximal k-degenerate graphs</a>, Discuss. Math. Graph Theory 32 4 (2012), 659-676.
%H Allan Bickle, <a href="https://doi.org/10.20429/tag.2024.000105">A Survey of Maximal k-degenerate Graphs and k-Trees</a>, Theory and Applications of Graphs 0 1 (2024) Article 5.
%H Sascha Stoll, <a href="https://limejuicestudio.com/pdf/Final_Master_thesis.pdf">On Subgraphs With Minimum Degree Restrictions</a>, Master's Thesis, Karlsruhe Institute of Technology, 2019.
%F rc(s,t) = ceiling(s + t - 3/2 + sqrt(2*(s-1)*(t-1) + 9/4)).
%e 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.
%e The square array begins:
%e 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
%e 3, 5, 6, 8, 9, 10, 12, 13, 14, 15, 17, ...
%e 4, 6, 8, 10, 11, 13, 14, 15, 17, 18, 19, ...
%e 5, 8, 10, 11, 13, 15, 16, 18, 19, 20, 22, ...
%e 6, 9, 11, 13, 15, 16, 18, 20, 21, 23, 24, ...
%e 7, 10, 13, 15, 16, 18, 20, 21, 23, 25, 26, ...
%e 8, 12, 14, 16, 18, 20, 22, 23, 25, 26, 28, ...
%t rc[s_,t_]:=Ceiling[s+t-3/2+Sqrt[2(s-1)(t-1)+9/4]]; Flatten[Table[rc[s-t+1,t],{s,12},{t,s}]] (* _Stefano Spezia_, Apr 03 2023 *)
%Y Cf. A361684 (rc(n,n)), A080036 (rc(2,n)).
%K nonn,tabl
%O 1,1
%A _Allan Bickle_, Mar 28 2023
|
