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

$$G=nP_2\cup P_{n+2}$$

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

$$f:V(G)\cup E(G)\to \{1,\dots,p+q\}$$

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

$$w_f(uv)=f(u)+f(uv)+f(v)$$

are exactly

$$\{a,a+d,\dots,a+(q-1)d\}.$$

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

For $n=1$,

$$G=P_2\cup P_3,$$

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

$$a,\ a+4,\ a+8.$$

The smallest possible edge-weight is

$$1+2+6=9,$$

and the largest possible edge-weight is

$$4+5+8=17.$$

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

$$13-7=6.$$

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

$$1+3,\ 2+3,\ 4+3,\ 5+3,$$

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.