MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

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 Hamming graph with $s^n$ points the sum is $$(a(s-2)+2)a(a^2(s-1)+1)^{n-1}.$$
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}.$$