Question

If G and H are graphs with n vertices, Δ(G,H) can be Θ(n²).

Here is an example which shows this. Let n=4k+1 be a prime. Define two graphs G=(V,E) and H=(V,FH=(V,E′) by V={0,1,2,…,4k}, E = {{i,j} | 1 ≤ ((j−i) mod n) ≤ k}, F E′ = {{i,j} | k+1 ≤ ((j−i) mod n) ≤ 2k}. Note that G and H are both unions of k edge-disjoint Hamiltonian circuits, which implies that α_i,j(G)=α_i,j(H)=2k for any distinct i and j. Let S={0,1,2,…,2k−1}. Then Δ(G,H) ≥ C_H(S)−C_G(S) = k(3k+1)−k(k+1) = 2k² = Θ(n²).

There is no reason to believe that this is the maximum of Δ(G,H) for given n, but it is obviously optimal up to a constant factor.