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

%I #45 Apr 18 2024 09:32:57

%S 3,4,7,9,12,15,19,22,28,31,38,42,49,54,62,67,77,82,93,99,110,117,129,

%T 136,150,157,172,180,195,204,220,229,247,256,275,285,304,315,335,346,

%U 368,379,402,414,437,450,474,487,513,526,553,567,594,609,637,652,682,697,728,744

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

%C 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.

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

%H Paolo Xausa, <a href="/A369568/b369568.txt">Table of n, a(n) for n = 3..10000</a>

%H Vacláv Chvátal, <a href="https://doi.org/10.1016/0095-8956(72)90020-2">On Hamilton's ideals</a>, J. Combin. Theory Ser. B 12(2): 163-168 (1972).

%H <a href="/index/Rec#order_09">Index entries for linear recurrences with constant coefficients</a>, signature (1,2,-2,-2,2,2,-2,-1,1).

%F 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.

%F From _Peter Luschny_, Jan 26 2024: (Start)

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

%F 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)

%e 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.

%p a:= n-> floor((3*n*(n+2)+(n mod 2)*(2*n-3))/16):

%p seq(a(n), n=3..62); # _Alois P. Heinz_, Jan 26 2024

%t A369568[n_] := Floor[(3*n*(n + 2) + Mod[n, 2] * (2*n - 3))/16];

%t Array[A369568, 100, 3] (* _Paolo Xausa_, Apr 18 2024 *)

%o (Python)

%o def a(n): return (n*(n + 1) - n//2*(n//2 - 1))//4

%o print([a(n) for n in range(3, 63)]) # _Peter Luschny_, Jan 26 2024

%o (Julia)

%o println([(n * (n + 1) - div(n, 2) * (div(n, 2) - 1)) ÷ 4 for n in 3:1000]) # _Paul Muljadi_, Jan 29 2024

%K nonn,easy

%O 3,1

%A _Don Knuth_, Jan 26 2024