Rikio Ichishima

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 for each $uv\in E\left( G\right) $. Also, $G$ is called super edge-magic if $f\left(V \left(G\right)\right) =\left\{1, 2, \ldots , \left\vert V\left( G\right) \right\vert \right\}$. Furthermore, 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$. In this paper, we introduce the parameter $l\left(n\right)$ as the minimum size of a graph $G$ of order $n$ for which all graphs of order $n$ and size at least $l\left(n\right)$ have $\mu_{s} \left( G \right)=+\infty $, and provide lower and upper bounds for $l\left(n\right)$. Imran, Baig, and Fe\u{n}ov\u{c}\'{i}kov\'{a} established that for integers $n$ with $n\equiv 0\pmod{4}$, $ \mu_{s}\left(D_{n}\right) \leq 3n/2-1$, where $D_{n}$ is the cartesian product of the cycle $C_{n}$ of order $n$ and the complete graph $K_{2}$ of order $2$. We improve this bound by showing that $ \mu_{s}\left(D_{n}\right) \leq n+1$ when $n \geq 4$ is even. Enomoto, Llad\'{o}, Nakamigawa, and Ringel posed the conjecture that every nontrivial tree is super edge-magic. We propose a new approach to attack this conjecture. This approach may also help to resolve another labeling conjecture on trees by Graham and Sloane.

A numbering $f$ of a graph $G$ of order $n$ is a labeling that assigns distinct elements of the set $\{1,2, \ldots, n \}$ to the vertices of $G$. The strength $\mathrm{str}\left(G\right) $ of $G$ is defined by $\mathrm{str}\left( G\right) =\min \left\{ \mathrm{str}_{f}\left( G\right)\left\vert f\text{ is a numbering of }G\right. \right\}$, where $\mathrm{str}_{f}\left( G\right) =\max \left\{ f\left( u\right) +f\left( v\right) \left\vert uv\in E\left( G\right) \right. \right\} $. A few lower and upper bounds for the strength are known and, although it is in general hard to compute the exact value for the strength, a reasonable approach to this problem is to study for which graphs a lower bound and an upper bound for the strength coincide. In this paper, we study general conditions for graphs that allow us to determine which graphs have the property that lower and upper bounds for the strength coincide and other graphs for which this approach is useless.

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 $ μ_{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 $ μ\left(G\right)$ of a graph $G$ is the smallest nonnegative integer $n$ for which $G\cup nK_{1}$ is edge-magic, being $ μ\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}$.

For all positive even integers $n$, graphs of order $n$ with degree sequence \begin{equation*} S_{n}:1,2,\dots,n/2,n/2,n/2+1,n/2+2,\dots,n-1 \end{equation*} naturally arose in the study of a labeling problem in \cite{IMO}. This fact motivated the authors of the aforementioned paper to study these sequences and as a result of this study they proved that there is a unique graph of order $n$ realizing $S_{n}$ for every even integer $n$. The main goal of this paper is to generalize this result.

Let $G$ be a graph of order $p$. A numbering $f$ of $G$ is a labeling that assigns distinct elements of the set $\left\{1,2,\dots ,p\right\}$ to the vertices of $G$, where each edge $uv$ of $G$ is labeled $f\left(u\right)+f\left(v\right)$. The strength str${}_f\left(G\right)$ of a numbering $f:V\left(G\right)\to \left\{1,2,\dots ,p\right\}$ of $G$ is defined by ${\mathrm{str}}_f\left(G\right)=max\left\{f\left(u\right)+f\left(v\right)\left|uv\in E\left(G\right)\right.\right\}\text{,}$ that is, ${\mathrm{str}}_f\left(G\right)$ is the maximum edge label of $G$, and the strength str$\left(G\right)$ of a graph $G$ itself is $\mathrm{str}\left(G\right)=min\left\{{\mathrm{str}}_f\left(G\right)\left|f\text{ is a numbering of }G\right.\right\}\text{.}$ The strengths $\mathrm{str}\left(T\right)$ and $\mathrm{str}\left(T_{n,k}\right)$ are determined for caterpillars $T$ and $k$-level complete $n$-ary trees $T_{n,k}$. The strength $\mathrm{str}\left(G\right)$ is also given for graphs $G$ obtained by taking the corona of certain graphs and an arbitrary number of isolated vertices. The work of this paper suggests an open problem on the strength of trees.

The beta-number of a graph $G$ is the smallest positive integer $n$ for which there exists an injective function $f:V\left(G\right)\to \left\{0,1,\dots ,n\right\}$ such that each $uv\in E\left(G\right)$ is labeled $|f\left(u\right)-f\left(v\right)|$ and the resulting set of edge labels is $\left\{c,c+1,\right.\left.\dots ,c+\left|E\left(G\right)\right|-1\right\}$ for some positive integer $c$. The beta-number of $G$ is $+\infty$ if there exists no such integer $n$. If $c=1$, then the resulting beta-number is called the strong beta-number of $G$. A galaxy is a forest for which each component is a star. In this paper, we establish a lower bound for the strong beta-number of an arbitrary galaxy under certain conditions. We also determine formulas for the (strong) beta-number and gracefulness of galaxies with three and four components. As corollaries of these results, we provide formulas for the beta-number and gracefulness of the disjoint union of multiple copies of the same galaxies if the number of copies is odd. Based on this work, we propose some problems and a new conjecture.