Akito Oshima

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.

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,\dots ,\right.\left.c+\left|E\left(G\right)\right|-1\right\}$ for some positive integer $c$. The beta-number of $G$ is $+\infty$, otherwise. If $c=1$, then the resulting beta-number is called the strong beta-number of $G$. A linear forest is a forest for which each component is a path. In this paper, we determine a formula for the (strong) beta-number of the linear forests with two components. This leads us to a partial formula for the beta-number of the disjoint union of multiple copies of the same linear forests.