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,1

Comments

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

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).

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

Example

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.

Mathematica

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

Prog

(Python)
print([5, 4, 3] + [1+(2*n-1)//7 for n in range(8, 80)]) # Gennady Eremin, Mar 07 2022
(PARI) a(n) = if(n<8, 10-n, (2*n+6)\7); \\ Kevin Ryde, Mar 08 2022

Crossrefs

Cf. A350716, A057356.

Sequence in context: A276052 A348340 A321028 * A263356 A061836 A021188

Adjacent sequences: A351166 A351167 A351168 * A351170 A351171 A351172

Keyword

nonn,easy

Author

Allan Bickle, Feb 03 2022

Status

approved