A Note On Magic Graphs

Abstract

By a $(1,1)$ edge-magic labeling of a graph $G(V,E)$, we mean a bijection $f$ from $V\cup E$ to $\{1,\dots ,|V|+|E|\}$ such that for all edges $uv\in E(G)$, the value $f(u)+f(v)+f(uv)$ is constant. We provide a different proof of a well-known result in additive number theory by Paul Erdős and, interestingly, demonstrate a practical application of this result. Additionally, we make some progress using computational methods towards the conjecture proposed by Yegnanarayanan: “Every graph on $p\ge 9$ vertices can be embedded as a subgraph of some $(1,1)$ edge-magic graph” raised by Yegnanarayanan.