2
$\begingroup$

A magic labeling of a simple graph $G$ is a labeling of the edges of $G$ with distinct positive integers such that the sum of the labels of the edges incident to a vertex is the same for each vertex. A graph that admits a magic labeling is said to be magic.

I found a characterization due to Stewart that the complete graph $K_n$ is supermagic if and only if $(n\geq6\text{ and }n\not\equiv0\mod{4})$ or $n=2$, and supermagic graphs are magic, but I can't seem to find a theorem deciding which complete graphs are merely magic.

$\endgroup$
  • 1
    $\begingroup$ You brought up supermagic but didn't define it. What is the definition of supermagic? $\endgroup$ – user2566092 Oct 8 '13 at 20:38
  • 1
    $\begingroup$ It's a graph with a supermagic labeling, which is a magic labeling in which the positive integers used are consecutive. $\endgroup$ – Jeh Oct 8 '13 at 20:41
2
$\begingroup$

Theorem $4.7$ of M. Doob, ‘Characterizations of regular magic graphs’, J. Combin. Theory, Ser. B $25$ $(1978)$ $94$-$104$ says that if $G$ is a regular graph with degree $d>4$ and $n$ vertices, then $G$ is magic if $d>\frac{n}2$. Since $n-1>\frac{n}2$ for $n>2$, this implies that $K_n$ is magic for all $n\ge 6$. Clearly $K_2$ is also magic and $K_3$ is not. Theorem $4.3(ii)$ of the same paper implies that $K_4$ is not magic, and unless I’m missing something, Theorem $4.3$ in its entirety implies that $K_5$ is magic.

$\endgroup$
  • $\begingroup$ I'm working on a labelling for $K_5$ because I've realised that the reference I found misses it out entirely, but I can't see where the construction would break down. $\endgroup$ – Peter Taylor Oct 8 '13 at 21:03
  • $\begingroup$ @Peter: Now that I’ve looked at the construction, I think that it does work for $K_5$: every pair of edges of $K_5$ is separated by a $4$-cycle. (By the way, you’ve a typo in the spoiler block after tweak: you have $3k$ instead of $3^k$.) $\endgroup$ – Brian M. Scott Oct 8 '13 at 21:13
  • $\begingroup$ It does work, and in fact it only takes the $4$ lexicographically first $4$-cycles. Thanks for the erratum, will correct. $\endgroup$ – Peter Taylor Oct 8 '13 at 21:16
1
$\begingroup$

It's strange that you can't find it, because the first page of results that Google gives me for magic graph include this set of exercises. Your question is exercise 1.3a.

Spoiler:

$K_n$ is magic for $n=2$ and $n\ge 5$.

(Note: this corrects the reference).


Leaving aside the small cases,

the proof for $n\ge 5$ is by the following construction. Since the graph is regular, we may consider arbitrary weights (not necessarily positive) and later add a suitably large constant to all of the edges.


I'm going to make a tweak to the proof.

Enumerate the cycles of length 4 that are contained in our graph, assigning them numbers from $1$ to $N$ (where $N$ is the total number of these cycles). Let the $k$th such cycle contribute $\pm 3^k$ (alternating) to its edges.


Let us check that this set of weights is magic. The total weight of the edges adjacent to every vertex is $0$, because the contribution of each cycle to this sum is $0$, so it suffices for the weights to be distinct. But for any pair of edges, there exists at least one cycle of length $4$ which includes only one of them. Therefore the sums of weights determined by the cycles are not equal, because the weights obtained by our construction may be regarded as $N$-digit balanced ternary numbers and so two edges can only have the same weight if they share all their $4$-cycles.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.