A351169 a(n) is the minimum number of vertices of degree 4 over all 4-collapsible graphs with n vertices.

5, 4, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 12, 12, 12, 12, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 16, 16, 16, 16, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 22, 22, 22

Offset: 5

Author

Allan Bickle, Feb 03 2022

Keywords

• nonn
• easy

Comments

A graph G is k-collapsible if it has minimum degree k and has no proper induced subgraph with minimum degree k.

Examples

			A complete graph with 5 vertices is 4-collapsible with 5 degree 4 vertices.
The graph formed by removing two nonadjacent edges from a complete graph with 6 vertices is 4-collapsible with 4 degree 4 vertices.
		

Links

• Gennady Eremin, Table of n, a(n) for n = 5..10000
• Allan Bickle, The k-Cores of a Graph, Ph.D. Dissertation, Western Michigan University (2010).
• Allan Bickle, Collapsible graphs, Congr. Numer. 231 (2018), 165-172.
• Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,0,0,1,-1).

Crossrefs

Cf. A350716, A057356.

Programs

Mathematica

A351169[n_]:=If[n<8,10-n,Ceiling[2n/7]];
Array[A351169,100,5] (* Paolo Xausa, Nov 30 2023 *)

PARI

a(n) = if(n<8,10-n,(2*n+6)\7); \\ Kevin Ryde, Mar 08 2022

Python

print([5,4,3] + [1+(2*n-1)//7 for n in range(8, 80)]) # Gennady Eremin, Mar 07 2022

Formula

a(n) = ceiling(2*n/7) for n > 7.

G.f.: x^5*(5 - x - x^2 + x^6 - 5*x^7 + x^8 + x^9 + x^10)/((1 - x)^2*(1 + x + x^2 + x^3 + x^4 + x^5 + x^6)). - Stefano Spezia, Feb 05 2022