A Proof of the Modular Edge-Graceful Trees Conjecture

Abstract

Let $G$ be a connected graph of order $n\ge 3$ and size $m$, and let $f:E(G)\to {\mathbb{Z}}_n$ be an edge labeling of $G$. Define an induced vertex labeling $f^{\prime }:V(G)\to {\mathbb{Z}}_n$ in terms of $f$ by $f^{\prime }(v)=\sum _{u\in N(v)}f(uv)$, where the sum is computed in ${\mathbb{Z}}_n$. If $f^{\prime }$ is one-to-one, then $f$ is called a modular edge-graceful labeling and $G$ is a modular edge-graceful graph. It is known that no connected graph of order $n\ge 3$ with $n\equiv 2(\mathrm{mod}4)$ is modular edge-graceful. A 1991 conjecture states that every tree of order $n$ where $n\not\equiv 2(\mathrm{mod}4)$ is modular edge-graceful. In this work, we show that this conjecture is true and furthermore that a nontrivial connected graph of order $n$ is modular edge-graceful if and only if $n\not\equiv 2(\mathrm{mod}4)$. The modular edge-gracefulness $\text{meg}(G)$ of a connected graph $G$ of order $n\ge 3$ is the smallest integer $k\ge n$ for which there exists an edge labeling $f:E(G)\to {\mathbb{Z}}_k$ such that the induced vertex labeling $f^{\prime }:V(G)\to {\mathbb{Z}}_k$ is one-to-one. It is shown that $\text{meg}(G)=n+1$ for every connected graph $G$ that is not modular edge-graceful.