Enumerating super edge-magic labelings for the union of non-isomorphic graphs

Authors

  • Ali Ahmad
  • Susana Clara Lopez
  • Francesc Antoni Muntaner-Batle
  • Miquel Rius-Font

Keywords:

Super edge-magic labeling, strong super edge-magic labeling

Abstract

A super edge-magic labeling of a graph $G = (V,E)$ of order $p$ and size $q$ is a bijection $f :V\cup E \rightarrow \{i\}_{i=1}^{p+q}$ such that (1) $f (u) + f (uv) + f (v) = k$ $\forall uv \in E$ and (2) $f (V) = \{i\}_{i=1}^{p}$. Furthermore, when $G$ is a linear forest, the super edge-magic labeling of $G$ is called \emph{strong} if it has the extra property that if $uv \in E(G),$ $u',v'\in V(G)$ and $d_G(u,u')=d_G(v,v')< +\infty,$ 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 non-necessarily 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.

Published

2011-10-19

Issue

Section

Articles