On super edge-magic deficiency of certain Toeplitz graphs

Year 2018, Volume: 47 Issue: 3, 513 - 519, 01.06.2018

Ali Ahmad , Muhammad Faisal Nadeem Ashok Gupta

Abstract

A graph $G$ is called edge-magic if there exists a bijective function $\phi:V(G)\cup E(G)\to\{1, 2,\dots,|V(G)|+|E(G)|\}$ such that $\phi(x)+\phi(xy)+\phi(y)=c(\phi)$ is a constant for every edge $xy\in E(G)$, called the valence of $\phi$. Moreover, $G$ is said to be super edge-magic if $\phi(V(G))=\{1,2,\dots,|V(G)|\}.$ The super edge-magic deficiency of a graph $G$, denoted by $\mu_s(G)$, is the minimum nonnegative integer $n$ such that $G\cup nK_1,$ has a super edge-magic labeling, if such integer does not exist we define $\mu_s(G)$ to be $+\infty.$ In this paper, we study the super edge-magic deficiency of some Toeplitz graphs.

Keywords

edge-magic, super edge-magic, Toeplitz graphs

References

• B. D. Acharya, S. M. Hegde, Strongly indexable graphs, Discrete Math., 93 (1991), 123129.
• A. Ahmad, I. Javaid , M. F. Nadeem and R. Hasni, On Super edge-magic deciency of some families related to ladder graphs, Australas. J. Combin., 51, 201208, 2011.
• A. Ahmad, M. Baca, M. F. Nadeem, On edge irregularity strength of Toeplitz graphs, U.P.B. Sci. Bull., Series A, 78(4), 155162, 2016.
• M. Baca, Y. Bashir, M. F. Nadeem, A. Shabbir, On super edge-antimagic total labeling of Toeplitz graphs, Springer Proceedings in Mathematics & Statistics, 98 (2015), 1-11.
• H. Enomoto, A. Lladó, T. Nakamigawa, and G. Ringel, Super edge-magic graphs, SUT J. Math., 34, 105109, 1998.
• R. M. Figueroa-Centeno, R. Ichishima and F.A. Muntaner-Batle, The place of super edge- magic labeling among other classes of labeling, Discrete Math., 231, 153168, 2001.
• R. M. Figueroa-Centeno, R. Ichishima and F.A. Muntaner-Batle, On the super edge-magic deciency of graphs, Electron. Notes Discrete Math., 11, 2002.
• R. M. Figueroa-Centeno, R. Ichishima and F.A. Muntaner-Batle, On the super edge-magic deciency of graphs, Ars Combin., 78, 2006.
• A. Kotzig and A. Rosa, Magic valuaton of nite graphs, Canad. Math. Bull., 13(4), 451461, 1970.
• A. A. G. Ngurah, R. Simanjuntak and E.T. Baskoro, On the super edge-magic deciencies of graphs, Australas. J. Combin., 40, 314, 2008.
• J.Y. Park, J.H. Choi and J.H. Bae, On super edge-magic labeling of some graphs, Bull. Korean Math. Soc., 45, No.1, 1121, 2008.