What is the sum at each vertex of a super-magic labeling of Kn,n? Explain your answer.

Question

What is the sum at each vertex of a super-magic labeling of Kn,n? Explain your answer.

I know that the sum at each vertex of K3,3 equals 15 and K4,4 the sum at each vertex is 34, but I don't know the pattern for all Kn,n.

Answer 1

A super-magic labeling (says the internet) of a graph is an edge weighting where the edge weights are consecutive integers (that’s the super part), and where if you label each vertex with the sum of the weights of its incident edges, you get the same label on each vertex.

In your $K_{3,3}$ example, the sum of the edge weights is $\frac{15\cdot6}{2}=45$, so the weights are the integers $1$ through $9$.

For a regular super-magic graph, if edge weights $w(e)$ create a super-magic labeling, so do edge weights $w'(e)=w(e)+c$ for any constant $c$.

Thus there are other super-magic labelings of $K_{3,3}$, say using the edge weights $2$ through $10$ for $K_{3,3}$, resulting in vertex sums of $18$. One can get all the vertex sums to be any multiple of $3$.

For your labeling of $K_{4,4}$, the sum of the edge weights is $\frac{34\cdot8}{2}=136=1+\cdots+16$, so the vertex sum (using regularity) is $\frac{136\cdot2}{8}=34$, and other super-magic labelings can result in vertex sums of $34\pm4k$ for any $k$.

Assuming there is a super-magic labeling of $K_{5,5}$, which has $25$ edges, there is one using the integers $1$ to $25$, so the sum at each vertex is $\frac{(1+\cdots+25)\cdot2}{10}$, or $65$, and other choices of $25$ consecutive integers can give any multiple of $5$. Can you develop a general answer by working along these lines?