As Gerhard points out, when the graph comes from a hyper-cube with $2^n$ points the sum is $2a(a^2+1)^{n-1}.$ When it comes from a Hammin graph with $s^n$ points the sum is $$(a(s-2)+2)a(a^2(s-1)+1)^{n-1}.$$
Aaron Meyerowitz
- 30.1k
- 1
- 48
- 104