×

On computing edge-magic graphs and \(Q(a)\) balance edge-magic graphs. (English) Zbl 1206.05082

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.)
PDFBibTeX XMLCite