Structural Properties and Labeling of Graphs

NEW

Problem: Let $P_m$ denote the path on $m$ vertices. The reconstructed assertion is:

For every $n\ge 1$ and each $d\in\{3,4\}$, the disconnected graph

admits a super $(a,d)$-edge-antimagic total labeling for some integer $a$.

Here a super $(a,d)$-edge-antimagic total labeling of a $(p,q)$-graph $G$ is a bijection

such that $f(V(G))=\{1,\dots,p\}$ and the edge-weights

are exactly

Result: The reconstructed universal existence statement is false. Already for $n=1$ and $d=4$, no such labeling exists.

For $n=1$,

so $p=5$, $q=3$. In a super labeling the vertex labels are $\{1,2,3,4,5\}$ and the edge labels are $\{6,7,8\}$.

If a super $(a,4)$-edge-antimagic total labeling existed, its three edge-weights would be

The smallest possible edge-weight is

and the largest possible edge-weight is

Since the required weight span is $8$, equality must hold throughout, so the edge of weight $9$ must use vertex labels $1,2$ and edge label $6$, while the edge of weight $17$ must use vertex labels $4,5$ and edge label $8$.

The remaining edge label is $7$, and the remaining weight must be $13$. Hence the remaining edge would need its two endpoint labels to sum to

But after using the disjoint vertex-label pairs $\{1,2\}$ and $\{4,5\}$, the only unused vertex label is $3$. In $P_2\cup P_3$, the remaining edge is incident to one vertex from either $\{1,2\}$ or $\{4,5\}$, so its vertex-label sum is one of

namely $4,5,7,$ or $8$, never $6$. Contradiction.

Thus $P_2\cup P_3$ has no super $(a,4)$-edge-antimagic total labeling. Therefore the claimed existence for all $n\ge1$ and $d\in\{3,4\}$ is false.

Citation: No literature citation is needed; the counterexample above is a direct finite verification.