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

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, 52, 54, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 92, 94, 96, 98, 100, 102, 104, 106, 108, 110, 112, 114, 116, 118, 120

Offset

1,3

Comments

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.

For n >= 10, any 4-regular triangle-free graph (i.e., graph with no three-cliques) will do.

For n = 9, there is no 4-regular triangle-free graph, as can be seen from inspection.

Links

Jörgen Backelin, Table of n, a(n) for n = 1..100

Index entries for linear recurrences with constant coefficients, signature (2,-1).

Formula

a(n) = floor(n^2/4) = A002620(n), if 1 <= n <= 8.

a(9) = 17.

a(n) = 2*n = A005843(n), if n >= 10.

From Chai Wah Wu, Feb 03 2021: (Start)

a(n) = 2*a(n-1) - a(n-2) for n > 11.

G.f.: x*(-x^10 + 2*x^9 - 3*x^8 + x^7 + x^5 + x^3 + x)/(x - 1)^2. (End)

Prog

(PARI) a(n)=if(n>9, 2*n, if(n<9, n^2\4, 17)) \\ Charles R Greathouse IV, Jan 06 2016

Crossrefs

Cf. A002620, A005843.

Sequence in context: A180107 A135146 A256956 * A258027 A053096 A155752

Adjacent sequences: A257634 A257635 A257636 * A257638 A257639 A257640

Keyword

easy,nonn

Author

Jörgen Backelin, Nov 04 2015

Status

approved