On Magic Strength of Graph

Abstract

Let $G=(V,E)$ be a finite simple graph. $G$ is said to be a magic graph iff there exists a magic assignment of $G$, which is a mapping $L$ from $E$ to $N=\{1,2,\dots \}$ such that the sums of the labels of all edges incident to the vertices in $V$ are identical. Let $M(G)$ be the set of all magic assignments of $G$. For any $L$ in $M(G)$, define $s(L)=max\{L(e):e\in E\}$. Then, the magic strength of $G$ is defined as $m(G)=min\{s(L):L\in M(G)\}$. In this paper, we determine the magic strengths of several classes of graphs and introduce some constructions of magic graphs. We also show that every connected graph is an induced subgraph of a magic graph.