If $K_n$ is super-magic, what is the sum at each vertex?

173 Views Asked by At

If $K_n$ is super-magic, what is the sum at each vertex?

A super-magic labeling 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.

1

There are 1 best solutions below

0
On BEST ANSWER

There are $\binom{n}{2}=\frac{n(n-1)}{2}$ edges in $K_n$, so the weights on the edges go from $1$ to $\frac{n(n-1)}{2}$. Since every edge is incident to exactly $2$ vertices, the edge weight gets counted in exactly two different sums at vertices. Now we have that there are $n$ vertices and that their sums (meaning the sum of the weights of their incident edges) are all equal to each other, so let's call this sum $S$. Now we count the total sum of all these individual vertex sums in two ways: $$nS=2\sum\limits_{e\in E(K_n)}w(e)$$

However, we know

$$\sum\limits_{e\in E(K_n)}w(e)=\sum\limits_{i=1}^{\frac{n(n-1)}{2}}i=\frac{\frac{n(n-1)}{2}\left(\frac{n(n-1)}{2}+1\right)}{2}$$

Hence we have $$S=\frac{(n-1)}{2}\left(\frac{n(n-1)}{2}+1\right)$$ We could also still write it in the binomial form if we wanted: $$S=\frac{1}{n}\binom{n}{2}\left(\binom{n}{2}+1\right)$$