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
KEYWORD
nonn,easy
AUTHOR
Allan Bickle, Feb 03 2022
STATUS
approved