A369568 Minimum number of edges that force an n-vertex graph to be Hamiltonian according to Chvátal's condition on the degree sequence.

3, 4, 7, 9, 12, 15, 19, 22, 28, 31, 38, 42, 49, 54, 62, 67, 77, 82, 93, 99, 110, 117, 129, 136, 150, 157, 172, 180, 195, 204, 220, 229, 247, 256, 275, 285, 304, 315, 335, 346, 368, 379, 402, 414, 437, 450, 474, 487, 513, 526, 553, 567, 594, 609, 637, 652, 682, 697, 728, 744

Offset

3,1

Comments

An optimum degree sequence begins with 2, 3, ..., n/2, and continues with n/2, when n is even, although the final term must be increased to n/2+1 if the sum is odd. It begins with 2, 3, ..., (n-1)/2, (n-1)/2, and continues with (n+1)/2, when n is odd, although the final term must be increased to (n+3)/2 if the sum is odd.

References

Donald E. Knuth, Hamiltonian paths and cycles, Prefascicle 8a of The Art of Computer Programming, Volume 4 (preprint, 2024).

Links

Paolo Xausa, Table of n, a(n) for n = 3..10000

Vacláv Chvátal, On Hamilton's ideals, J. Combin. Theory Ser. B 12(2): 163-168 (1972).

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

Formula

a(n) = floor((3*n^2+6*n)/16) if n is even, a(n) = floor((3*n^2+8*n-3)/16) if n is odd.

From Peter Luschny, Jan 26 2024: (Start)

a(n) = floor([x^n] ((x - 2)*x^2*(x + 1) - x) / (2*(x + 1)^2 * (x - 1)^3)).

G.f.: (x^2*(x^6 - x^5 - 2*x^4 + x^3 + x^2 - 2*x - 1))/((x - 1)^3 * (x + 1)^2 * (x^4 + 1)). (End)

Example

For n=11 a graphical degree sequence meeting Chvátal's condition and having smallest sum is 2,3,4,5,5,6,6,6,6,6,7; so the minimum number of edges, a(11), is (2+3+4+5+5+6+6+6+6+6+7)/2=28.

Maple

a:= n-> floor((3*n*(n+2)+(n mod 2)*(2*n-3))/16):
seq(a(n), n=3..62);  # Alois P. Heinz, Jan 26 2024

Mathematica

A369568[n_] := Floor[(3*n*(n + 2) + Mod[n, 2] * (2*n - 3))/16];
Array[A369568, 100, 3] (* Paolo Xausa, Apr 18 2024 *)

Prog

(Python)
def a(n): return (n*(n + 1) - n//2*(n//2 - 1))//4
print([a(n) for n in range(3, 63)])  # Peter Luschny, Jan 26 2024
(Julia)
println([(n * (n + 1) - div(n, 2) * (div(n, 2) - 1)) ÷ 4 for n in 3:1000]) # Paul Muljadi, Jan 29 2024

Crossrefs

Sequence in context: A246514 A060142 A049844 * A248358 A244952 A140402

Adjacent sequences: A369565 A369566 A369567 * A369569 A369570 A369571

Keyword

nonn,easy

Author

Don Knuth, Jan 26 2024

Status

approved