Recent studies on the super edge-magic deficiency of graphs

PASS

The claimed disproof is valid. For $D_6\cup K_1$, the given vertex labels are exactly $\{1,\dots,13\}$, and the 18 edge endpoint-sums are exactly $5,\dots,22$. Hence assigning edge labels $36-(f(u)+f(v))$ gives exactly $\{14,\dots,31\}$ and constant magic sum $36$. Thus $D_6\cup K_1$ is super edge-magic, so $\mu_s(D_6)\le 1<7=6+1$, contradicting the proposed equality for even $n\ge6$.

Novelty assessment

KNOWN

Classification rationale: The negative resolution is already implied by older graph-labeling literature. Jungreis–Reid proved that $C_{4m+2}\times P_{2n}$ is sequential. Taking $m=n=1$ gives $D_6=C_6\square K_2=C_6\times P_2$ sequential. A sequential labeling of a graph with $p$ vertices and $q$ edges immediately gives a super edge-magic labeling of $G\cup(q-p)K_1$. Thus $D_6\cup 6K_1$ is super edge-magic, so $\mu_s(D_6)\le 6<7$, already refuting the proposed equality $\mu_s(D_n)=n+1$ for all even $n\ge6$. The submitted $D_6\cup K_1$ labeling may be a sharper small-case construction, but the resolution of the stated problem is not new.

Literature check: Gallian’s Dynamic Survey defines sequential/strongly harmonious labelings and records Jungreis–Reid’s result that $C_{4m+2}\times P_{2n}$ is sequential. Since $K_2\cong P_2$, this covers $D_6$. The standard edge-sum characterization of super edge-magic labelings converts this directly to a known counterexample to Problem 1.

Citation: D. Jungreis and M. Reid, “Labeling grids,” Ars Combinatoria 34 (1992), 167–182. See also J. A. Gallian, “A Dynamic Survey of Graph Labeling,” Electron. J. Combin. Dynamic Survey DS6, §4.1, summarizing the sequential-labeling result.