login
A351169
a(n) is the minimum number of vertices of degree 4 over all 4-collapsible graphs with n vertices.
2
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
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.
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
Sequence in context: A374420 A348340 A321028 * A263356 A061836 A021188
KEYWORD
nonn,easy
AUTHOR
Allan Bickle, Feb 03 2022
STATUS
approved