Strong Labelings of Linear Forests

NEW

Problem: Reconstructed statement: for every $K\ge 1$, if

is a disjoint union of an even number of finite path-like trees, all of the same order, with $T_j\not\cong P_2$, then $G$ is super edge-magic. Here a $(p,q)$-graph is super edge-magic if there is a bijection

such that $f(V(G))=\{1,\dots,p\}$ and $f(u)+f(uv)+f(v)$ is constant over all edges $uv$.

This is the literal content of Open Problem 3. Paths are path-like trees under the standard definition, since $P_n$ is obtained from an embedding of $P_n$ by zero elementary transformations.

Result: The statement is false. Take

Then $K=1$, both components are path-like trees of order $3$, and neither is $P_2$.

Suppose $2P_3$ were super edge-magic. Let the two degree-$2$ vertices, one in each copy of $P_3$, have vertex labels $x,y$. Since $p=6$ and $q=4$, the four endpoint sums

must be four consecutive integers, say

Also,

But the sum of the four consecutive endpoint sums is $4t+6$, so

Since $x,y$ are distinct labels from $\{1,\dots,6\}$, we have $3\le x+y\le 11$, hence $t\in\{5,6\}$.

If $t=5$, then $x+y=5$. The required endpoint sum $5$ can only arise from the label pairs $\{1,4\}$ or $\{2,3\}$, which must be exactly the two center labels. But the two centers lie in different components and are not adjacent, so no edge has endpoint sum $5$, contradiction.

If $t=6$, then $x+y=9$. The required endpoint sum $9$ can only arise from $\{3,6\}$ or $\{4,5\}$, again exactly the two center labels. They are not adjacent, so no edge has endpoint sum $9$, contradiction.

Thus $2P_3$ is not super edge-magic, so Open Problem 3 has a negative answer as stated.

The defect is a small boundary omission: $2P_2$ is excluded, but $2P_3$ must also be excluded if a positive theorem is intended.

Citation: Problem and terminology: M. Bača, Y. Q. Lin, F. A. Muntaner-Batle, M. Rius-Font, “Strong labelings of linear forests,” Acta Mathematica Sinica, English Series 25 (2009), 1951–1964, doi:10.1007/s10114-009-8284-3.