On the super edge-magicness and the deficiency of some families of acyclic graphs (Q2831596)

Let \(G\) be a graph of order \(p\) and size \(q\). A bijection \(f:V(G)\cup E(G) \to \{1,2,3,\ldots, p+q\}\) is called a super edge-magic total labeling of \(G\) if there exists a constant \(s\) such that \(f(V(G))=\{1,2,3,\ldots p\}\) and \(f(u)+f(v)+f(uv)=s\) for every \(uv\in E(G)\). The minimum non-negative integer \(n\) such that \(G\cup nK_1\) has a super edge-magic total labeling is called the super edge-magic deficiency of \(G\). In this paper, the authors discuss the existence of super edge-magic total labeling and hence the super edge-magic deficiency for certain types of forests consisting of paths \(P_n\), stars \(K_{1,n}\), comb graphs \(Cb_n\) and extended \(w\)-trees \(Ewt(n,k,r)\).NEWLINENEWLINENEWLINEThe first graph \(G\) under consideration is the union of a comb graph \(Cb_m\) and an extended \(w\)-tree \(Ewt(n,k,r)\). For the graph \(G\cong Cb_m\cup Ewt(n,k,r)\), with \(r,k\geq 3\) and \(m\leq rk+1\), the authors prove that {\parindent=0.6cm\begin{itemize}\item[(a)] \(G\) admits super edge-magic total labeling, if \(n>\frac{r(k-2)}{2}\) when \(k\) is even and \(n>\frac{r(k-1)}{2}\) when \(k\) is odd; \item[(b)] \(G\) admits super edge-magic total labeling, if \(n=\frac{r(k-2)}{2}\) for even \(k\), \(m\neq r-1,r(k-1)+1\); \item[(c)] \(G\) admits super edge-magic total labeling, if \(n=\frac{r(k-1)}{2}\) for odd \(k\), \(m\neq r(k-1)+1\). NEWLINENEWLINE\end{itemize}}NEWLINENEWLINEThe second graph discussed is the union of a star graph \(K_{1,m}\) and an extended \(w\)-tree \(Ewt(n,k,r)\). It is shown that the graph \(K_{1,m}\cup Ewt(n,k,r)\) admits a super edge-magic labeling if {\parindent=0.6cm\begin{itemize}\item[(a)] \(n>\frac{r(k-2)}{2}\) when \(k\) is even and \(n>\frac{r(k-1)}{2}\) when \(k\) is odd and \(m\neq \alpha r\); \item[(b)] \(n=\frac{r(k-2)}{2}\) for even \(k\), \(m\neq r-1,r(k-1)+1\) and \(m\neq \alpha r\); \item[(c)] \(n=\frac{r(k-1)}{2}\) for odd \(k\), \(m\neq r(k-1)+1\) and \(m\neq \alpha r\). NEWLINENEWLINE\end{itemize}}NEWLINENEWLINEIn this theorem, it is also proved that, in all the three cases mentioned above, the super edge magic deficiency is less than or equal to \(1\), when \(m=\alpha r\). The third case discussed in this article is of admissibility of super edge-magic total labeling by the union of paths and extended \(w\)-trees. The authors prove that the graph \(P_m\cup Ewt(n,k,r)\), with \(r,k\geq 3\), \(3\leq m\leq 2rk+1\) and \(m\) odd, admits a super edge-magic total labeling ifNEWLINENEWLINE{\parindent=0.6cm\begin{itemize}\item[(a)] \(n>\frac{r(k-2)}{2}\) when \(k\) is even and \(n>\frac{r(k-1)}{2}\) when \(k\) is odd; \item[(b)] \(n=\frac{r(k-2)}{2}\) for even \(k\), \(m\neq 2r-3, 2r(k-1)+1\); and \item[(c)] \(n=\frac{r(k-1)}{2}\) for even \(k\), \(m\neq 2r(k-1)+1\). NEWLINENEWLINE\end{itemize}}NEWLINENEWLINEThe fourth and final result states that the graph \(P_m\cup Ewt(n,k,r)\), with \(r,k\geq 3\), \(2\leq m\leq 2rk\) and \(m\) odd, admits a super edge-magic total labeling ifNEWLINENEWLINE{\parindent=0.6cm\begin{itemize}\item[(a)] \(n>\frac{r(k-2)}{2}\) when \(k\) is even and \(n>\frac{r(k-1)}{2}\) when \(k\) is odd and \(m\neq 2\alpha r\); \item[(b)] \(n=\frac{r(k-2)}{2}\) for even \(k\), \(m\neq 2(r-1),2r(k-1)+2\) and \(m\neq 2\alpha r\); \item[(c)] \(n=\frac{r(k-1)}{2}\) for odd \(k\), \(m\neq 2r(k-1)+2\) and \(m\neq \alpha r\). NEWLINENEWLINE\end{itemize}}NEWLINENEWLINESimilar to the second result in the paper, the authors prove that, in all the three cases mentioned above, the super edge magic deficiency is less than or equal to \(1\), when \(m=2\alpha r\).NEWLINENEWLINEAll four results in the paper are logical and interesting. The proofs of these results are lengthy and split into many cases and subcases. The authors deserve much appreciation for their contribution in this very good paper.