Chung, Ping-Tsai; Lee, Sin-Min On computing edge-magic graphs and \(Q(a)\) balance edge-magic graphs. (English) Zbl 1206.05082 Congr. Numerantium 199, 153-165 (2009). Summary: If \(G\) is a \((p,q)\)-graph in which the edges are labeled \(1,2,3,\dots,q\) so that the vertex sums are constant, \(\text{mod\,}p\), then \(G\) is called an Edge-Magic graph (in short, EM graph). A \((p,q)\)-graph \(G\) in which the edges are labeled by \(Q(a)\) so that the vertex sums are constant \(\mod p\), is a called \(Q(a)\) Balance Edge-Magic graph (in short, \(Q(a)\)-BEM graph), where for \(a \geq 1\), we denote \[ Q(a)= \begin{cases} \{\pm a,\dots,\pm(a- 1+ q/2)\}\quad &\text{if }q\text{ is even},\\ \{0,\pm a,\dots,\pm(a- 1+ (q-1)/2)\},\quad &\text{if }q\text{ is odd}. \end{cases} \]Our purpose of this paper is to show that the theory of EM graphs and the theory of \(Q(a)\)-BEM graphs are unrelated. Particularly, we investigate that some graphs are both EM and \(Q(a)\)-BEM graphs; Some \(Q(a)\)-BEM graphs which are not EM; Infinitely many non-\(Q(a)\)-BEM graphs which are not EM. Several conjectures are proposed. Finally, we show that both the EM graph problem and \(Q(a)\)-BEM graph problem are NP-hard. MSC: 05C78 Graph labelling (graceful graphs, bandwidth, etc.) Keywords:edge-magic; , \(Q(a)\) balance edge-magic; strong BEM; NP-hard PDFBibTeX XMLCite \textit{P.-T. Chung} and \textit{S.-M. Lee}, Congr. Numerantium 199, 153--165 (2009; Zbl 1206.05082)