×

Super edge magic graceful graphs. (English) Zbl 1355.05212

Summary: A \((p, q)\) graph \(G\) with \( p\) vertices and \(q\) edges is edge magic graceful if there exists a bijection \(f : V(G) \cup E(G) \to \{1, 2, \ldots, p + q \}\) such that \(| f(u) + f(v) - f({uv}) | = k\), a constant for any edge \( uv\) of \( G\). \(G\) is said to be super edge magic graceful if \(f(V(G)) = \{1, 2, \ldots, p \}\). In this paper we present some properties of super edge magic graceful graphs. Using these properties, we prove some classes of graphs are super edge magic graceful. Then we exhibit the relationship between super edge magic graceful labeling and other well studied classes of labelings. In particular, we prove that every super edge magic graceful graph with either \(f({uv}) > f(u) + f(v)\) for all \({uv} \in E(G)\) or \(f({uv}) < f(u) + f(v)\) for all \({uv} \in E(G)\) is sequential, harmonious, super edge magic and not graceful.

MSC:

05C78 Graph labelling (graceful graphs, bandwidth, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahmad, A.; Baig, A. Q.; Imran, M., On super edge-magicness of graphs, Util. Math., 89, 373-380 (2012) · Zbl 1270.05084
[2] Ali, K.; Hussain, M.; Razzaq, A., Super edge-magic total labeling of a tree, Util. Math., 91, 355-364 (2013) · Zbl 1300.05274
[3] Baig, A. Q.; Afzal, H. U.; Imran, M.; Javaid, I., Super edge-magic labeling of volvox and pancyclic graphs, Util. Math., 93, 49-56 (2014) · Zbl 1293.05330
[4] Ball, M. O.; Golden, B. L.; Vohra, R. V., Finding the most vital arcs in a network, Oper. Res. Lett., 8, 73-76 (1989) · Zbl 0679.90086
[5] Corley, H. W.; Sha, D. Y., Most vital links and nodes in weighted networks, Oper. Res. Lett., 1, 157-160 (1982) · Zbl 0488.90069
[6] Enomota, H.; Llado, A. S.; Nakamigawa, T.; Ringel, G., Super edge-magic graphs, SUT J. Math., 34, 105-109 (1998) · Zbl 0918.05090
[7] Figueroa-Centeno, R. M.; Ichishima, R.; Muntaner-Batle, F. A., The place of super edge-magic labelings among other classes of labelings, Discrete Math., 231, 153-168 (2001) · Zbl 0977.05120
[8] Gallian, J. A., A dynamic survey of graph labeling, Electron. J. Combin., 18, #DS6 (2011) · Zbl 0953.05067
[9] Golomb, S. W., How to number a graph, (Road, R. C., Graph Theory and Computing (1972), Academic press: Academic press New York), 23-37 · Zbl 0293.05150
[10] Grace, T., On sequential labelings of graphs, J. Graph Theory, 7, 195-201 (1983) · Zbl 0522.05063
[11] Graham, R. L.; Sloane, N. J.A., On additive bases and harmonious graphs, SIAM J. Alg. Discrete Meth., 1, 382-404 (1980) · Zbl 0499.05049
[12] Hsu, L. H.; Jan, R. H.; Lee, Y. C.; Hung, C. N.; Chern, M. S., Finding the most vital edge with respect to minimum spanning tree in weighted graphs, Inform. Process. Lett., 39, 277-281 (1991) · Zbl 0749.68043
[13] Hoede, C.; Kuiper, H., All wheels are graceful, Util. Math., 14, 311 (1978) · Zbl 0397.05048
[14] Ichishima, R.; Muntaner-Batle, F. A.; Oshima, A., Enlarging the classes of super edge-magic 2-regular graphs, AKCE Int. J. Graphs Comb., 10, 2, 129-146 (2013) · Zbl 1301.05294
[15] Javaid, M.; Bhatti, A. A.; Hussain, M.; Ali, K., Super edge-magic total labeling on forest of extended \(w\)-trees, Util. Math., 91, 155-162 (2013) · Zbl 1300.05275
[16] Javaid, M.; Hussain, M.; Ali, K.; Shaker, H., On super edge-magic total labeling on subdivision of trees, Util. Math., 89, 169-177 (2012) · Zbl 1267.05230
[17] Kotzig, A.; Rosa, A., Magic valuation of finite graphs, Can. Math. Bull., 13, 451-461 (1970) · Zbl 0213.26203
[18] Lopez, S. C.; Muntaner-Batle, F. A.; Rius-Font, M., New problems related to the valences of (super) edge-magic labeling, AKCE Int. J. Graphs Comb., 10, 2, 169-181 (2013) · Zbl 1301.05299
[19] Lopez, S. C.; Muntaner-Batle, F. A.; Rius-Font, M., The jumping knight and other (super) edge-magic constructions, Mediterr. J. Math., 11, 217-235 (2014) · Zbl 1294.05138
[21] Sedlacek, J., On magic graphs, Math. Slov., 26, 329-335 (1976) · Zbl 0348.05114
[22] Lee, Sin-Min; Wang, Yung-Chin, On super edge-magicness of chain graphs whose blocks are complete graphs, Congr. Numer., 162, 147-160 (2003) · Zbl 1046.05070
[23] Stewart, B. M., Magic graphs, Can. J. Math., 18, 1031-1059 (1966) · Zbl 0149.21401
[24] Wallis, W. D., Magic Graphs (2001), Birkhauser: Birkhauser Boston · Zbl 0979.05001
[25] Zhenbin, G.; Chongjin, F., Some discussions on super edge-magic labeling of \(St(a_1, \ldots, a_n)\), Ars Combin., 108, 187-192 (2013) · Zbl 1289.05414
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.