On The Super Edge-graceful Spiders of Even Orders

Abstract

A $(p,q)$-graph $G$ is said to be $\mathbf{\text{edge graceful}}$ if the edges can be labeled by $1,2,\dots ,q$ so that the vertex sums are distinct, mod $p$. It is shown that if a tree $T$ is edge-graceful, then its order must be odd. Lee conjectured that all trees of odd orders are edge-graceful. J. Mitchem and A. Simoson introduced the concept of super edge-graceful graphs, which is a stronger concept than edge-graceful for some classes of graphs.

A graph $G=(V,E)$ of order $p$ and size $q$ is said to be $\mathbf{\text{super edge-graceful}}$ (SEG) if there exists a bijection
$$\text{f: E}\to \{\begin{array}{ll}\{0,+1,-1,+2,-2,\dots ,\frac{q-1}{2},-\frac{q-1}{2}\}& \text{if }q\text{ is odd}\\ \{+1,-1,+2,-2,\dots ,\frac{q}{2},-\frac{q}{2}\}& \text{if }q\text{ is even}\end{array}$$
such that the induced vertex labeling $f^{\ast }$ defined by $f^{\ast }(u)=\sum \{f(u,v):(u,v)\in E\}$ has the property:
$$f^{\ast }:V\to \{\begin{array}{ll}\{0,+1,-1,\dots ,+\frac{p-1}{2},-\frac{p-1}{2}\}& \text{if }p\text{ is odd}\\ \{+1,-1,\dots ,+\frac{p}{2},-\frac{p}{2}\}& \text{if }p\text{ is even}\end{array}$$
is a bijection.

The conjecture is still unsettled. In this paper, we first characterize spiders of even orders which are not SEG. We then exhibit some spiders of even orders which are SEG of diameter at most four. By the concepts of the irreducible part of an even tree $T$, we show that an infinite number of spiders of even orders are SEG. Finally, we provide some conjectures for further research.