Rikio Ichishima, Francesc Muntaner-Batle, Yukio Takahashi: Some new results concerning the valences of (super) edge-magic graphs, 185-200

Abstract:

A graph $G$ is called edge-magic if there exists a bijective function $f:V\left(G\right) \cup E\left(G\right)\rightarrow \left\{1, 2, \ldots , \left\vert V\left( G\right) \right\vert +\left\vert E\left( G\right) \right\vert \right\}$ such that $f\left(u\right) + f\left(v\right) + f\left(uv\right)$ is a constant (called the valence of $f$) for each $uv\in E\left( G\right)$. If $f\left(V \left(G\right)\right) =\left\{1, 2, \ldots , \left\vert V\left( G\right) \right\vert \right\}$, then $G$ is called a super edge-magic graph. A stronger version of edge-magic and super edge-magic graphs appeared when the concepts of perfect edge-magic and perfect super edge-magic graphs were introduced. The super edge-magic deficiency $\mu_{s}\left(G\right)$ of a graph $G$ is defined to be either the smallest nonnegative integer $n$ with the property that $G \cup nK_{1}$ is super edge-magic or $+ \infty$ if there exists no such integer $n$. On the other hand, the edge-magic deficiency $\mu\left(G\right)$ of a graph $G$ is the smallest nonnegative integer $n$ for which $G \cup nK_{1}$ is edge-magic, being $\mu\left(G\right)$ always finite. In this paper, the concepts of (super) edge-magic deficiency are generalized using the concepts of perfect (super) edge-magic graphs. This naturally leads to the study of the valences of edge-magic and super edge-magic labelings. We present some general results in this direction and study the perfect (super) edge-magic deficiency of the star $K_{1,n}$.

Key Words: Perfect (super) edge-magic labeling, perfect (super) edge-magic deficiency, valence, graph labeling, combinatorial optimazation.

2020 Mathematics Subject Classification: Primary 05C78; Secondary 90C27.

Download the paper in pdf format here.