cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A257637 Maximal number of edges in an n-vertex triangle-free graph with maximal degree at most 4.

This page as a plain text file.
%I A257637 #31 Feb 03 2021 21:55:06
%S A257637 0,1,2,4,6,9,12,16,17,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50,
%T A257637 52,54,56,58,60,62,64,66,68,70,72,74,76,78,80,82,84,86,88,90,92,94,96,
%U A257637 98,100,102,104,106,108,110,112,114,116,118,120
%N A257637 Maximal number of edges in an n-vertex triangle-free graph with maximal degree at most 4.
%C A257637 For n <= 8, a(n) is the Turan number T(3,n), realized by a complete bipartite graph K(m, m) if n = 2m or K(m, m+1) if n = 2m+1, since then that graph has maximal degree <= 4.
%C A257637 For n >= 10, any 4-regular triangle-free graph (i.e., graph with no three-cliques) will do.
%C A257637 For n = 9, there is no 4-regular triangle-free graph, as can be seen from inspection.
%H A257637 Jörgen Backelin, <a href="/A257637/b257637.txt">Table of n, a(n) for n = 1..100</a>
%H A257637 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (2,-1).
%F A257637 a(n) = floor(n^2/4) = A002620(n), if 1 <= n <= 8.
%F A257637 a(9) = 17.
%F A257637 a(n) = 2*n = A005843(n), if n >= 10.
%F A257637 From _Chai Wah Wu_, Feb 03 2021: (Start)
%F A257637 a(n) = 2*a(n-1) - a(n-2) for n > 11.
%F A257637 G.f.: x*(-x^10 + 2*x^9 - 3*x^8 + x^7 + x^5 + x^3 + x)/(x - 1)^2. (End)
%o A257637 (PARI) a(n)=if(n>9, 2*n, if(n<9, n^2\4, 17)) \\ _Charles R Greathouse IV_, Jan 06 2016
%Y A257637 Cf. A002620, A005843.
%K A257637 easy,nonn
%O A257637 1,3
%A A257637 _Jörgen Backelin_, Nov 04 2015