Hostname: page-component-78c5997874-j824f Total loading time: 0 Render date: 2024-11-17T14:17:02.728Z Has data issue: false hasContentIssue false
  • English
  • Français

ENUMERATING SUPER EDGE-MAGIC LABELINGS FOR THE UNION OF NONISOMORPHIC GRAPHS

Part of: Graph theory

Published online by Cambridge University Press:  15 June 2011

A. AHMAD ,
S. C. LÓPEZ ,
F. A. MUNTANER-BATLE  and
M. RIUS-FONT
A. AHMAD
Affiliation:
Department of Mathematics, Govt. College University, Lahore, Pakistan (email: [email protected])
S. C. LÓPEZ*
Affiliation:
Departament de Matemàtica Aplicada IV, Universitat Politècnica de Catalunya, C/Esteve Terrades 5, 08860 Castelldefels, Spain (email: [email protected])
F. A. MUNTANER-BATLE
Affiliation:
Graph Theory and Applications Research Group, School of Electrical Engineering and Computer Science, Faculty of Engineering and Built Environment, The University of Newcastle, NSW 2308, Australia (email: [email protected])
M. RIUS-FONT
Affiliation:
Departament de Matemàtica Aplicada IV, Universitat Politècnica de Catalunya, C/Esteve Terrades 5, 08860 Castelldefels, Spain (email: [email protected])
*
✉For correspondence; e-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

A super edge-magic labeling of a graph G=(V,E) of order p and size q is a bijection f:V ∪E→{i}p+qi=1 such that: (1) f(u)+f(uv)+f(v)=k for all uv∈E; and (2) f(V )={i}pi=1. Furthermore, when G is a linear forest, the super edge-magic labeling of G is called strong if it has the extra property that if uv∈E(G) , u′,v′ ∈V (G) and dG (u,u′ )=dG (v,v′ )<+∞, then f(u)+f(v)=f(u′ )+f(v′ ). In this paper we introduce the concept of strong super edge-magic labeling of a graph G with respect to a linear forest F, and we study the super edge-magicness of an odd union of nonnecessarily isomorphic acyclic graphs. Furthermore, we find exponential lower bounds for the number of super edge-magic labelings of these unions. The case when G is not acyclic will be also considered.

Keywords

super edge-magic labelingstrong super edge-magic labeling

MSC classification

Secondary: 05C78: Graph labelling (graceful graphs, bandwidth, etc.)
Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 84 , Issue 2 , October 2011 , pp. 310 - 321
Copyright
Copyright © Australian Mathematical Publishing Association Inc. 2011

Footnotes

The research conducted in this document by second and forth author has been supported by the Spanish Research Council under project MTM2008-06620-C03-01 and by the Catalan Research Council under grant 2009SGR1387.

References

[1]Acharya, B. D. and Hegde, S. M., ‘Strongly indexable graphs’, Discrete Math. 93 (1991), 123–129.CrossRefGoogle Scholar
[2]Bača, M., Lin, Y. and Muntaner-Batle, F. A., ‘Super edge-antimagic labelings of the path-like trees’, Util. Math. 73 (2007), 117–128.Google Scholar
[3]Bača, M., Lin, Y. and Muntaner-Batle, F. A., ‘Normalized embeddings of path-like trees’, Util. Math. 78 (2009), 11–31.Google Scholar
[4]Bača, M., Lin, Y., Muntaner-Batle, F. A. and Rius-Font, M., ‘Strong labelings of linear forests’, Acta Math. Sin. (Engl. Ser.) 25(12) (2009), 1951–1964.CrossRefGoogle Scholar
[5]Bača, M. and Miller, M., Super Edge-Antimagic Graphs (Brown Walker Press, Boca Raton, FL, 2008).Google Scholar
[6]Barrientos, C., ‘Difference vertex labelings’, PhD Thesis, Universitat Politècnica de Catalunya, 2004.Google Scholar
[7]Chartrand, G. and Lesniak, L., Graphs and Digraphs, 3rd edn (CRC Press, Boca Raton, FL, 1996).Google Scholar
[8]Enomoto, H., Lladó, A. S., Nakamigawa, T. and Ringel, G., ‘Super edge-magic graphs’, SUT J. Math. 34 (1998), 105–109.CrossRefGoogle Scholar
[9]Figueroa-Centeno, R. M., Ichishima, R. and Muntaner-Batle, F. A., ‘The place of super edge-magic labeling among other classes of labeling’, Discrete Math. 231 (2001), 153–168.CrossRefGoogle Scholar
[10]Figueroa-Centeno, R. M., Ichishima, R., Muntaner-Batle, F. A. and Rius-Font, M., ‘Labeling generating matrices’, J. Combin. Math. Combin. Comput. 67 (2008), 189–216.Google Scholar
[11]Kotzig, A. and Rosa, A., ‘Magic valuations of finite graphs’, Canad. Math. Bull. 13 (1970), 451–461.CrossRefGoogle Scholar
[12]López, S. C., Muntaner-Batle, F. A. and Rius-Font, M., ‘Enumerating super edge-magic labelings for some types of path-like trees’, submitted.Google Scholar
[13]Muntaner-Batle, F. A. and Rius-Font, M., ‘On the structure of path-like trees’, Discuss. Math. Graph Theory 28(2) (2008), 249–265.CrossRefGoogle Scholar
[14]Ringel, G. and Lladó, A., ‘Another tree conjecture’, Bull. Inst. Combin. Appl. 18 (1996), 83–85.Google Scholar
[15]Wallis, W. D., Magic Graphs (Birkhäuser, Boston, MA, 2001).CrossRefGoogle Scholar
[16]West, D. B., Introduction to Graph Theory (Prentice Hall, Upper Saddle River, NJ, 1996).Google Scholar