read(`C11.txt`): # uses MinMaxNNpablo to compute the independence number of a graph G=[n,E] IndNu:=proc(G) local i: i:=1: while (i+1<=G[1]) and MinMaxNNpablo(G,i+1)=0 do: i++: od: i: end: ################################### # CHALLENGE: # The independence number of Gnd is floor(n/(d+1)) # # Proof: # Observe that Gnd is the d-th power graph of the C_n (the cycle graph on n vertices). # In particular, finding the independence number is the same as finding the maximum number # of vertices on C_n which are distance > d. We can achieve this greedily by taking # {1,1+(d+1),1+2(d+1),...,1+k(d+1)} where k is max such that (n+1)-(1+k(d+1)) >= d+1. Note that k+1 # will be the independence number. We obtain the condition k+1<= n/(d+1) # Since k+1 must be an integer, the bound is equivalent to k+1<= floor(n/(d+1)). QED. ################################### ##### # UpperBoundMinMaxNN(Ck(8),129,5000) = 7. ##### UpperBoundMinMaxNN:= proc(G,r,K) local mini,V,H,i,curr: V:={seq(i,i=1..G[1])}: H:=randcomb(V,r): mini:=MaxNN(G,H): for i from 2 to K do: H:=randcomb(V,r): curr:= MaxNN(G,H): if curr < mini then: mini:=curr: fi: od: mini: end: