On the strong beta-number of galaxies with three and four components

Abstract

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.

Keywords:

• Beta-number
• Strong beta-number
• Graph labeling
• $\beta$-valuation
• Graceful labeling

1 Introduction

All graphs considered in this paper are finite and undirected without loops or multiple edges. The vertex set of a graph $G$ is denoted by $V\left(G\right)$, while the edge set is denoted by $E\left(G\right)$. The union $G_1\cup G_2$ of two subgraphs $G_1$ and $G_2$ of a graph $G$ is the subgraph with vertex set $V\left(G_1\right)\cup V\left(G_2\right)$ and edge set $E\left(G_1\right)\cup E\left(G_2\right)$. The union of any finite number of subgraphs is defined similarly.

For integers $a$ and $b$ with $a\le b$, the set $\left\{x\in \mathbb{Z}:a\le x\le b\right\}$ will be denoted by writing $\left[a,b\right]$, where $\mathbb{Z}$ denotes the set of all integers. On the other hand, if $a>b$, then we treat $\left[a,b\right]$ as the empty set. If such a situation appears in particular formulas for a given vertex labeling, then we ignore the corresponding portions of the formulas.

As a possible way of attacking graph decomposition problems, $\beta$-valuations were originated by Rosa [1]. For a graph $G$ of size $q$, an injective function $f:V\left(G\right)\to \left[0,q\right]$ is called a $\beta$-valuation if each $uv\in E\left(G\right)$ is labeled $|f\left(u\right)-f\left(v\right)|$ and the resulting edge labels are distinct. Such a valuation is now commonly known as a graceful labeling (the term was coined by Golomb [2]) and a graph with a graceful labeling is called graceful. Graceful labelings have been the focus of many papers. For recent contributions to this subject and other types of labelings, the authors refer the reader to the survey by Gallian [3].

The gracefulness, grac$\left(G\right)$, of a graph $G$ was introduced by Golomb [2] as the smallest positive integer $n$ for which there exists an injective function $f:V\left(G\right)\to \left[0,n\right]$ such that each $uv\in E\left(G\right)$ is labeled $|f\left(u\right)-f\left(v\right)|$ and the resulting edge labels are distinct. It is clear that if $G$ is a graph of size $q$ with grac$\left(G\right)=q$, then $G$ is graceful. Thus, the gracefulness of a graph $G$ is a parameter that measures how close $G$ is to being graceful.

A number of authors have invented analogues of gracefulness. For instance, the beta-number and strong beta-number introduced in [4] are such type of parameters. The beta-number, $\beta \left(G\right)$ , of a graph $G$ with $q$ edges is the smallest positive integer $n$ for which there exists an injective function $f:V\left(G\right)\to \left[0,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+q-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$ and is denoted by ${\beta }_s\left(G\right)$.

The following result observed in [4] summarizes how the parameters discussed thus far are related.

Lemma 1

For every graph $G$ of order $p$ and size $q$, $$max\left\{p-1,q\right\}\le \mathrm{grac}\left(G\right)\le \beta \left(G\right)\le {\beta }_s\left(G\right)\text{.}$$

A galaxy is a forest for which each component is a star. In [4] the authors determined the exact values for the (strong) beta-number for several classes of graphs including galaxies with two components, and proved that every nontrivial tree and forest has finite strong beta-number. Ichishima et al. [5] studied the (strong) beta-number for forests with isomorphic components. This led them to conjecture that the (strong) beta-number and gracefulness of a forest of order $p$ are either $p-1$ or $p$ . They further obtained the following result, which will prove to be useful later.

Theorem 1

If $F$ is a forest of order $p$ such that $\beta \left(F\right)=p-1$, then $$\beta \left(mF\right)=mp-1$$when $m$ is odd.

In this paper, we present 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. These results add credence to the mentioned conjectures, and lead us to propose some problems and a new conjecture on the strong beta-number of galaxies.

There are other kinds of parameters that measure how close a graph is to being graceful. For further knowledge on the (strong) beta-number of graphs and related concepts, the authors suggest that the reader consults the results found in [6–10]. For the most recent advances on the mentioned conjectures, the authors also direct the reader to the papers [5,11].

2 General result

Our first result of this paper provides a lower bound for the strong beta-number of an arbitrary galaxy. For the purpose of presenting this result, we denote the star with $n+1$ vertices by $S_n$.

Theorem 2

Let $G\cong S_{n_1}\cup S_{n_2}\cup \cdots \cup S_{n_k}$. If$n_1{n}_2\cdots n_k$ is odd, and $k\equiv 2$ or$3(mod4)$, then${\beta }_s\left(G\right)\ge m+k$, where$m=n_1+n_2+\cdots +n_k$.

Proof

We prove the logically equivalent contrapositive statement of the theorem, that is, we show that if ${\beta }_s\left(G\right)\le m+k-1$, then $n_1{n}_2\cdots n_k$ is even, or $k\equiv 0$ or $1(mod4)$. Thus, assume that $n_1{n}_2\cdots n_k$ is odd ($n_i$ is odd for each $i\in \left[1,k\right]$), and we will then verify that $k\equiv 0$ or $1(mod4)$. By our assumption, there exists an injective function $f:V\left(G\right)\to \left[0,m+k-1\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[1,m\right]$.

Now, define the galaxy $G$ with $$V\left(G\right)=\left\{x_i:i\in \left[1,k\right]\right\}\cup \left(\bigcup _{i=1}^k\left\{y_i^{j\left(i\right)}:j\left(i\right)\in \left[1,n_i\right]\right\}\right)$$and $E\left(G\right)={\bigcup }_{i=1}^k\left\{x_i{y}_i^{j\left(i\right)}:j\left(i\right)\in \left[1,n_i\right]\right\}$. Let $f\left(x_i\right)=c_i$ for each $i\in \left[1,k\right]$. For each $i\in \left[1,k\right]$, let $f\left(y_i^{j\left(i\right)}\right)=a_i^{j\left(i\right)}$ with $a_i^{j\left(i\right)}>c_i$ ($j\left(i\right)\in \left[1,s_i\right]$), and let $f\left(y_i^{j\left(i\right)}\right)=b_i^{j\left(i\right)}$ with $b_i^{j\left(i\right)}<c_i$ ($j\left(i\right)\in \left[1,t_i\right]$). Then $$\frac{\left(m+k-1\right)\left(m+k\right)}{2}=\sum _{v\in V\left(G\right)}f\left(v\right)=\sum _{i=1}^k{c}_i+\sum _{i=1}^k\sum _{j\left(i\right)=1}^{s_i}{a}_i^{j\left(i\right)}+\sum _{i=1}^k\sum _{j\left(i\right)=1}^{t_i}{b}_i^{j\left(i\right)}$$ and $$\frac{m\left(m+1\right)}{2}=\sum _{uv\in E\left(G\right)}|f\left(u\right)-f\left(v\right)|=\sum _{i=1}^k\sum _{j\left(i\right)=1}^{s_i}\left(a_i^{j\left(i\right)}-c_i\right)+\sum _{i=1}^k\sum _{j\left(i\right)=1}^{t_i}\left(c_i-b_i^{j\left(i\right)}\right)\text{.}$$ Summing the above two equations together with the fact that $n_i=s_i+t_i$ ($i\in \left[1,k\right]$), we obtain $$m^2+km+\frac{k\left(k-1\right)}{2}=\sum _{i=1}^k{c}_i+\sum _{i=1}^k\sum _{j\left(i\right)=1}^{s_i}\left(2a_i^{j\left(i\right)}-c_i\right)+\sum _{i=1}^k\sum _{j\left(i\right)=1}^{t_i}{c}_i=\sum _{i=1}^k\left(s_i+t_i+1\right)c_i+2\sum _{i=1}^k\left(\sum _{j\left(i\right)=1}^{s_i}{a}_i^{j\left(i\right)}-s_i{c}_i\right)=\sum _{i=1}^k\left(n_i+1\right)c_i+2\sum _{i=1}^k\left(\sum _{j\left(i\right)=1}^{s_i}{a}_i^{j\left(i\right)}-s_i{c}_i\right)\text{.}$$ Recall that $n_i$ is odd for each $i\in \left[1,k\right]$. This implies that $$\sum _{i=1}^k\left(n_i+1\right)c_i+2\sum _{i=1}^k\left(\sum _{j\left(i\right)=1}^{s_i}{a}_i^{j\left(i\right)}-s_i{c}_i\right)$$is even; so $m^2+km+k\left(k-1\right)∕2$ is even. It is straightforward to see that if $k\equiv 2$ or $3(mod4)$, then $m^2+km+k\left(k-1\right)∕2$ is odd. Therefore, $k\equiv 0$ or $1(mod4)$, and the proof is completed. □

3 Results on galaxies with three components

In this section, we first prove the following theorem, which shows in this case that the bound given in Theorem 2 is sharp.

Theorem 3

For any positive integers $n_1$,$n_2$ and$n_3$, $${\beta }_s\left(S_{n_1}\cup S_{n_2}\cup S_{n_3}\right)=\left\{\begin{array}{cc}{n}_1+n_2+n_3+2\hfill & \text{if}{n}_1{n}_2{n}_3\text{is even},\hfill \\ n_1+n_2+n_3+3\hfill & \text{if}{n}_1{n}_2{n}_3\text{is odd}.\hfill \end{array}\right.$$

Proof

For positive integers $n_1$, $n_2$ and $n_3$, let $G\cong S_{n_1}\cup S_{n_2}\cup S_{n_3}$ be the galaxy with $$V\left(G\right)=\left\{x_i:i\in \left[1,3\right]\right\}\cup \left(\bigcup _{i=1}^3\left\{y_i^{j\left(i\right)}:j\left(i\right)\in \left[1,n_i\right]\right\}\right)$$and $E\left(G\right)={\bigcup }_{i=1}^3\left\{x_i{y}_i^{j\left(i\right)}:j\left(i\right)\in \left[1,n_i\right]\right\}$. It follows immediately from Lemma 1 that ${\beta }_s\left(G\right)\ge n_1+n_2+n_3+2$.

To verify that ${\beta }_s\left(G\right)\le n_1+n_2+n_3+2$, suppose that $n_1{n}_2{n}_3$ is even, and consider the following two cases for the vertex labeling $f:V\left(G\right)\to \left[0,n_1+n_2+n_3+2\right]$.

Case 1. For $n_1=2k_1$, $n_2=2k_2$ and $n_3=2k_3$, where $k_1$, $k_2$ and $k_3$ are positive integers, let $$f\left(x_i\right)=\left\{\begin{array}{cc}i-1\hfill & \text{if}i\in \left[1,2\right],\hfill \\ 2k_1+2k_2+2k_3+2\hfill & \text{if}i=3,\hfill \end{array}\right.$$$$f\left(y_1^{j\left(1\right)}\right)=\left\{\begin{array}{cc}{k}_2+1+j\left(1\right)\hfill & \text{if}j\left(1\right)\in \left[1,k_1\right],\hfill \\ k_2+2k_3+j\left(1\right)\hfill & \text{if}j\left(1\right)\in \left[k_1+1,2k_1\right],\hfill \end{array}\right.$$$$f\left(y_2^{j\left(2\right)}\right)=\left\{\begin{array}{cc}1+j\left(2\right)\hfill & \text{if}j\left(2\right)\in \left[1,k_2\right],\hfill \\ 2k_1+2k_3+1+j\left(2\right)\hfill & \text{if}j\left(2\right)\in \left[k_2+1,2k_2\right],\hfill \end{array}\right.$$$$f\left(y_3^{j\left(3\right)}\right)=\left\{\begin{array}{cc}{k}_1+k_2+1+j\left(3\right)\hfill & \text{if}j\left(3\right)\in \left[1,2k_3-1\right],\hfill \\ 2k_1+k_2+2k_3+1\hfill & \text{if}j\left(3\right)=2k_3.\hfill \end{array}\right.$$ Notice then that $$\left\{f\left(y_1^{j\left(1\right)}\right):j\left(1\right)\in \left[1,k_1\right]\right\}=\left[k_2+2,k_1+k_2+1\right]\text{,}$$$$\left\{f\left(y_1^{j\left(1\right)}\right):j\left(1\right)\in \left[k_1+1,2k_1\right]\right\}=\left[k_1+k_2+2k_3+1,2k_1+k_2+2k_3\right]\text{,}$$$$\left\{f\left(y_2^{j\left(2\right)}\right):j\left(2\right)\in \left[1,k_2\right]\right\}=\left[2,k_2+1\right]\text{,}$$$$\left\{f\left(y_2^{j\left(2\right)}\right):j\left(2\right)\in \left[k_2+1,2k_2\right]\right\}=\left[2k_1+k_2+2k_3+2,2k_1+2k_2+2k_3+1\right]\text{,}$$$$\left\{f\left(y_3^{j\left(3\right)}\right):j\left(3\right)\in \left[1,2k_3-1\right]\right\}=\left[k_1+k_2+2,k_1+k_2+2k_3\right]\text{,}$$$$\left\{f\left(y_3^{j\left(3\right)}\right):j\left(3\right)=2k_3\right\}=\left\{2k_1+k_2+2k_3+1\right\}\text{.}$$ This together with the values of $f\left(x_1\right)$, $f\left(x_2\right)$ and $f\left(x_3\right)$ implies that $f$ is a bijective function. Notice also that $$\left\{|f\left(x_1\right)-f\left(y_1^{j\left(1\right)}\right)|:j\left(1\right)\in \left[1,k_1\right]\right\}=\left[k_2+2,k_1+k_2+1\right]\text{,}$$$$\left\{|f\left(x_1\right)-f\left(y_1^{j\left(1\right)}\right)|:j\left(1\right)\in \left[k_1+1,2k_1\right]\right\}=[k_1+k_2+2k_3+1,2k_1+k_2+2k_3]\text{,}$$$$\left\{|f\left(x_2\right)-f\left(y_2^{j\left(2\right)}\right)|:j\left(2\right)\in \left[1,k_2\right]\right\}=\left[1,k_2\right]\text{,}$$$$\left\{|f\left(x_2\right)-f\left(y_2^{j\left(2\right)}\right)|:j\left(2\right)\in \left[k_2+1,2k_2\right]\right\}=[2k_1+k_2+2k_3+1,2k_1+2k_2+2k_3]\text{,}$$$$\left\{|f\left(x_3\right)-f\left(y_3^{j\left(3\right)}\right)|:j\left(3\right)\in \left[1,2k_3-1\right]\right\}=\left[k_1+k_2+2,k_1+k_2+2k_3\right]\text{,}$$$$\left\{|f\left(x_3\right)-f\left(y_3^{j\left(3\right)}\right)|:j\left(3\right)=2k_3\right\}=\left\{k_2+1\right\}\text{.}$$ Thus, $$\left\{|f\left(u\right)-f\left(v\right)|:uv\in E\left(G\right)\right\}=\left[1,\left|E\left(G\right)\right|\right]\text{,}$$since $\left|E\left(G\right)\right|=2k_1+2k_2+2k_3$. Consequently, ${\beta }_s\left(G\right)\le n_1+n_2+n_3+2$ when $n_1$, $n_2$ and $n_3$ is even.

Case 2. For $n_1=k_1$, $n_2=2k_2$ and $n=2k_3-1$, where $k_1$, $k_2$ and $k_3$ are positive integers, let $$f\left(x_i\right)=\left\{\begin{array}{cc}i-1\hfill & \text{if}i\in \left[1,2\right],\hfill \\ k_1+2k_2+2k_3+1\hfill & \text{if}i=3,\hfill \end{array}\right.$$$$f\left(y_1^{j\left(1\right)}\right)=\begin{array}{cc}{k}_2+k_3+j\left(1\right)\hfill & \text{if}j\left(1\right)\in \left[1,k_1\right],\hfill \end{array}$$$$f\left(y_2^{j\left(2\right)}\right)=\left\{\begin{array}{cc}1+j\left(2\right)\hfill & \text{if}j\left(2\right)\in \left[1,k_2\right],\hfill \\ k_1+2k_3+j\left(2\right)\hfill & \text{if}j\left(2\right)\in \left[k_2+1,2k_2\right],\hfill \end{array}\right.$$$$f\left(y_3^{j\left(3\right)}\right)=\left\{\begin{array}{cc}{k}_2+1+j\left(3\right)\hfill & \text{if}j\left(3\right)\in \left[1,k_3-1\right],\hfill \\ k_1+k_2+1+j\left(3\right)\hfill & \text{if}j\left(3\right)\in \left[k_3,2k_3-1\right],\hfill \end{array}\right.$$ Notice then that $$\left\{f\left(y_1^{j\left(1\right)}\right):j\left(1\right)\in \left[1,k_1\right]\right\}=\left[k_2+k_3+1,k_1+k_2+k_3\right]\text{,}$$$$\left\{f\left(y_2^{j\left(2\right)}\right):j\left(2\right)\in \left[1,k_2\right]\right\}=\left[2,k_2+1\right]\text{,}$$$$\left\{f\left(y_2^{j\left(2\right)}\right):j\left(2\right)\in \left[k_2+1,2k_2\right]\right\}=\left[k_1+k_2+2k_3+1,k_1+2k_2+2k_3\right]\text{,}$$$$\left\{f\left(y_3^{j\left(3\right)}\right):j\left(3\right)\in \left[1,k_3-1\right]\right\}=\left[k_2+2,k_2+k_3\right]\text{,}$$$$\left\{f\left(y_3^{j\left(3\right)}\right):j\left(3\right)\in \left[k_3,2k_3-1\right]\right\}=\left[k_1+k_2+k_3+1,k_1+k_2+2k_3\right]\text{.}$$ This together with the values of $f\left(x_1\right)$, $f\left(x_2\right)$ and $f\left(x_3\right)$ implies that $f$ is a bijective function. Notice also that $$\left\{|f\left(x_1\right)-f\left(y_1^{j\left(1\right)}\right)|:j\left(1\right)\in \left[1,k_1\right]\right\}=\left[k_2+k_3+1,k_1+k_2+k_3\right]\text{,}$$$$\left\{|f\left(x_2\right)-f\left(y_2^{j\left(2\right)}\right)|:j\left(2\right)\in \left[1,k_2\right]\right\}=\left[1,k_2\right]\text{,}$$$$\left\{|f\left(x_2\right)-f\left(y_2^{j\left(2\right)}\right)|:j\left(2\right)\in \left[k_2+1,2k_2\right]\right\}=[k_1+k_2+2k_3,k_1+2k_2+2k_3-1]\text{,}$$$$\left\{|f\left(x_3\right)-f\left(y_3^{j\left(3\right)}\right)|:j\left(3\right)\in \left[1,k_3-1\right]\right\}=[k_1+k_2+k_3+1,k_1+k_2+2k_3-1]\text{,}$$$$\left\{|f\left(x_3\right)-f\left(y_3^{j\left(3\right)}\right)|:j\left(3\right)\in \left[k_3,2k_3-1\right]\right\}=\left[k_2+1,k_2+k_3\right]\text{.}$$ Thus, $$\left\{|f\left(u\right)-f\left(v\right)|:uv\in E\left(G\right)\right\}=\left[1,\left|E\left(G\right)\right|\right]\text{,}$$since $\left|E\left(G\right)\right|=k_1+2k_2+2k_3-1$. Consequently, ${\beta }_s\left(G\right)\le n_1+n_2+n_3+2$ when $n_1$ is arbitrary, $n_2$ is even and $n_3$ is odd. It is now immediate that ${\beta }_s\left(G\right)=n_1+n_2+n_3+2$ when $n_1{n}_2{n}_3$ is even.

Next, suppose that $n_1{n}_2{n}_3$ is odd. Then, by Theorem 2, ${\beta }_s\left(G\right)\ge n_1+n_2+n_3+3$. It only remains to establish that ${\beta }_s\left(G\right)\le n_1+n_2+n_3+3$ when $n_1{n}_2{n}_3$ is odd. Thus, let $n_1=2k_1-1$, $n_2=2k_2-1$, $n_3=2k_3-1$, where $k_1$, $k_2$ and $k_3$ are positive integers, and consider the vertex labeling $g:V\left(G\right)\to \left[0,n_1+n_2+n_3+3\right]$ such that $$g\left(x_i\right)=\left\{\begin{array}{cc}i-1\hfill & \text{if}i\in \left[1,2\right],\hfill \\ 2k_1+2k_2+2k_3\hfill & \text{if}i=3,\hfill \end{array}\right.$$$$g\left(y_1^{j\left(1\right)}\right)=\begin{array}{cc}{k}_2+k_3+j\left(1\right)\hfill & \text{if}j\left(1\right)\in \left[1,2k_1-1\right],\hfill \end{array}$$$$g\left(y_2^{j\left(2\right)}\right)=\left\{\begin{array}{cc}1+j\left(2\right)\hfill & \text{if}j\left(2\right)\in \left[1,k_2\right],\hfill \\ 2k_1+2k_3-1+j\left(2\right)\hfill & \text{if}j\left(2\right)\in \left[k_2+1,2k_2-1\right],\hfill \end{array}\right.$$$$g\left(y_3^{j\left(3\right)}\right)=\left\{\begin{array}{cc}{k}_2+1+j\left(3\right)\hfill & \text{if}j\left(3\right)\in \left[1,k_3-1\right],\hfill \\ 2k_1+k_2+j\left(3\right)\hfill & \text{if}j\left(3\right)\in \left[k_3,2k_3-1\right].\hfill \end{array}\right.$$ Notice then that $$\left\{g\left(y_1^{j\left(1\right)}\right):j\left(1\right)\in \left[1,2k_1-1\right]\right\}=\left[k_2+k_3+1,2k_1+k_2+k_3-1\right]\text{,}$$$$\left\{g\left(y_2^{j\left(2\right)}\right):j\left(2\right)\in \left[1,k_2\right]\right\}=\left[2,k_2+1\right]\text{,}$$$$\left\{g\left(y_2^{j\left(2\right)}\right):j\left(2\right)\in \left[k_2+1,2k_2-1\right]\right\}=\left[2k_1+k_2+2k_3,2k_1+2k_2+2k_3-2\right]\text{,}$$$$\left\{g\left(y_3^{j\left(3\right)}\right):j\left(3\right)\in \left[1,k_3-1\right]\right\}=\left[k_2+2,k_2+k_3\right]\text{,}$$$$\left\{g\left(y_3^{j\left(3\right)}\right):j\left(3\right)\in \left[k_3,2k_3-1\right]\right\}=\left[2k_1+k_2+k_3,2k_1+k_2+2k_3-1\right]\text{.}$$ This together with the values of $g\left(x_1\right)$, $g\left(x_2\right)$ and $g\left(x_3\right)$ implies that $g$ is an injective function. Notice also that $$\left\{|g\left(x_1\right)-g\left(y_1^{j\left(1\right)}\right)|:j\left(1\right)\in \left[1,2k_1-1\right]\right\}=[k_2+k_3+1\text{,}2k_1+k_2+k_3-1]\text{,}$$$$\left\{|g\left(x_2\right)-g\left(y_2^{j\left(2\right)}\right)|:j\left(2\right)\in \left[1,k_2\right]\right\}=\left[1,k_2\right]\text{,}$$$$\left\{|g\left(x_2\right)-g\left(y_2^{j\left(2\right)}\right)|:j\left(2\right)\in \left[k_2+1,2k_2-1\right]\right\}=[2k_1+k_2+2k_3,2k_1+2k_2+2k_3-3]\text{,}$$$$\left\{|g\left(x_3\right)-g\left(y_3^{j\left(3\right)}\right)|:j\left(3\right)\in \left[1,k_3-1\right]\right\}=[2k_1+k_2+k_3,2k_1+k_2+2k_3-1]\text{,}$$$$\left\{|g\left(x_3\right)-g\left(y_3^{j\left(3\right)}\right)|j\left(3\right)\in \left[k_3,2k_3-1\right]\right\}=\left[k_2+1,k_2+k_3\right]\text{.}$$ Thus, $$\left\{|g\left(u\right)-g\left(v\right)|:uv\in E\left(G\right)\right\}=\left[1,\left|E\left(G\right)\right|\right]\text{,}$$since $\left|E\left(G\right)\right|=2k_1+2k_2+2k_3-3$. Consequently, ${\beta }_s\left(G\right)\le n_1+n_2+n_3+3$ when $n_1{n}_2{n}_3$ is odd. The desired result now follows. □

With the aid of Theorem 3, it is now possible to determine the beta-number of galaxies with three components.

Theorem 4

For any positive integers $n_1$,$n_2$ and$n_3$, $$\beta \left(S_{n_1}\cup S_{n_2}\cup S_{n_3}\right)=n_1+n_2+n_3+2\text{.}$$

Proof

For positive integers $n_1$, $n_2$ and $n_3$, let $G\cong S_{n_1}\cup S_{n_2}\cup S_{n_3}$ be the galaxy defined as in the proof of the preceding theorem. In light of Theorem 3 and Lemma 1, it suffices to verify that $\beta \left(G\right)\le n_1+n_2+n_3+2$ when $n_1{n}_2{n}_3$ is odd. Thus, let $n_i=2k_i-1$, where $k_i$ is a positive integer for each $i\in \left[1,3\right]$, and consider the vertex labeling $f:V\left(G\right)\to \left[0,n_1+n_2+n_3+2\right]$ such that $$f\left(x_i\right)=\left\{\begin{array}{cc}0\hfill & \text{if}i=1,\hfill \\ 2k_1+2k_2+2k_3-4+i\hfill & \text{if}i\in \left[2,3\right],\hfill \end{array}\right.$$$$f\left(y_1^{j\left(1\right)}\right)=\left\{\begin{array}{cc}2k_1+2k_2+k_3-2\hfill & \text{if}j\left(1\right)=1\text{,}\hfill \\ k_2+k_3-2+j\left(1\right)\hfill & \text{if}j\left(1\right)\in \left[2,k_1\right]\text{,}\hfill \\ k_2+k_3-1+j\left(1\right)\hfill & \text{if}j\left(1\right)\in \left[k_1+1,2k_1-1\right]\text{,}\hfill \end{array}\right.$$$$f\left(y_2^{j\left(2\right)}\right)=\left\{\begin{array}{cc}{k}_3+j\left(2\right)\hfill & \text{if}j\left(2\right)\in \left[1,k_2-1\right],\hfill \\ k_1+k_2+k_3-1\hfill & \text{if}j\left(2\right)=k_2,\hfill \\ 2k_1+k_3-2+j\left(2\right)\hfill & \text{if}j\left(2\right)\in \left[k_2+1,2k_2-1\right],\hfill \end{array}\right.$$$$f\left(y_3^{j\left(3\right)}\right)=\left\{\begin{array}{cc}1+j\left(3\right)\hfill & \text{if}j\left(3\right)\in \left[1,k_3-1\right],\hfill \\ 1\hfill & \text{if}j\left(3\right)=k_3,\hfill \\ 2k_1+2k_2-2+j\left(3\right)\hfill & \text{if}j\left(3\right)\in \left[k_3+1,2k_3-1\right].\hfill \end{array}\right.$$ It remains to observe that $f$ leads us to conclude that $\beta \left(G\right)\le n_1+n_2+n_3+2$, which yields the desired result. □

The next result follows immediately from Theorems 1 and 4.

Corollary 1

For any positive integers $n_1$,$n_2$ and$n_3$, $$\beta \left(m\left(S_{n_1}\cup S_{n_2}\cup S_{n_3}\right)\right)=m\left(n_1+n_2+n_3+3\right)-1\text{,}$$where $m$ is odd.

The following result is now obtained from Theorem 4 and Lemma 1.

Corollary 2

For any positive integers $n_1$,$n_2$ and$n_3$, $$\mathrm{grac}\left(S_{n_1}\cup S_{n_2}\cup S_{n_3}\right)=n_1+n_2+n_3+2\text{.}$$

The following result is a simple consequence of Corollary 1 and Lemma 1.

Corollary 3

For any positive integers $n_1$,$n_2$ and$n_3$, $$\mathrm{grac}\left(m\left(S_{n_1}\cup S_{n_2}\cup S_{n_3}\right)\right)=m\left(n_1+n_2+n_3+3\right)-1\text{,}$$where $m$ is odd.

4 Results on galaxies with four components

In this section, we present formulas for the (strong) beta-number of galaxies with four components and related results. We start with the following theorem.

Theorem 5

For any positive integers $n_1$,$n_2$,$n_3$ and$n_4$, $${\beta }_s\left(S_{n_1}\cup S_{n_2}\cup S_{n_3}\cup S_{n_4}\right)=n_1+n_2+n_3+n_4+3\text{.}$$

Proof

For positive integers $n_1$, $n_2$, $n_3$ and $n_4$, let $G\cong S_{n_1}\cup S_{n_2}\cup S_{n_3}\cup S_{n_4}$ be the galaxy with $$V\left(G\right)=\left\{x_i:i\in \left[1,4\right]\right\}\cup \left(\bigcup _{i=1}^4\left\{y_i^{j\left(i\right)}:j\left(i\right)\in \left[1,n_i\right]\right\}\right)$$and $E\left(G\right)={\bigcup }_{i=1}^4\left\{x_i{y}_i^{j\left(i\right)}:j\left(i\right)\in \left[1,n_i\right]\right\}$. In light of Lemma 1, it suffices to show that ${\beta }_s\left(G\right)\le n_1+n_2+n_3+n_4+3$. Thus, consider the following cases for the vertex labeling $f:V\left(G\right)\to \left[0,n_1+n_2+n_3+n_4+3\right]$.

Case 1. For $n_i=2k_i$, where $k_i$ is a positive integer for each $i\in \left[1,4\right]$, let $$f\left(x_i\right)=\left\{\begin{array}{cc}i-1\hfill & \text{if}i\in \left[1,3\right],\hfill \\ 2k_1+2k_2+2k_3+2k_4+3\hfill & \text{if}i=4,\hfill \end{array}\right.$$$$f\left(y_1^{j\left(1\right)}\right)=\left\{\begin{array}{cc}{k}_2+k_3+2+j\left(1\right)\hfill & \text{if}j\left(1\right)\in \left[1,k_1\right],\hfill \\ k_2+k_3+2k_4+j\left(1\right)\hfill & \text{if}j\left(1\right)\in \left[k_1+1,2k_1\right],\hfill \end{array}\right.$$$$f\left(y_2^{j\left(2\right)}\right)=\left\{\begin{array}{cc}{k}_3+2+j\left(2\right)\hfill & \text{if}j\left(2\right)\in \left[1,k_2\right],\hfill \\ 2k_1+k_3+2k_4+1+j\left(2\right)\hfill & \text{if}j\left(2\right)\in \left[k_2+1,2k_2\right],\hfill \end{array}\right.$$$$f\left(y_3^{j\left(3\right)}\right)=\left\{\begin{array}{cc}2+j\left(3\right)\hfill & \text{if}j\left(3\right)\in \left[1,k_3\right],\hfill \\ 2k_1+2k_2+2k_4+2+j\left(3\right)\hfill & \text{if}j\left(3\right)=\left[k_3+1,2k_3\right],\hfill \end{array}\right.$$$$f\left(y_4^{j\left(4\right)}\right)=\left\{\begin{array}{cc}{k}_1+k_2+k_3+2+j\left(4\right)\hfill & \text{if}j\left(4\right)\in \left[1,2k_4-2\right],\hfill \\ 2k_1+k_2+k_3+2k_4+1\hfill & \text{if}j\left(4\right)=2k_4-1\text{,}\hfill \\ 2k_1+2k_2+k_3+2k_4+2\hfill & \text{if}j\left(4\right)=2k_4.\hfill \end{array}\right.$$ Case 2. For $n_1=n_2=1$, $n_3=k_3$ and $n_4=k_4$, where $k_3$ and $k_4$ are positive integers, assume, without loss of generality, that $k_3\ge k_4$ and let $$f\left(x_i\right)=\left\{\begin{array}{cc}0\hfill & \text{if}i=1,\hfill \\ i\hfill & \text{if}i\in \left[2,3\right],\hfill \\ 2k_4+5\hfill & \text{if}i=4,\hfill \end{array}\right.$$$$f\left(y_1^{j\left(1\right)}\right)=\begin{array}{c}1,\hfill \end{array}$$$$f\left(y_2^{j\left(2\right)}\right)=2k_4+4\text{,}$$$$f\left(y_3^{j\left(3\right)}\right)=\left\{\begin{array}{cc}3+2j\left(3\right)\hfill & \text{if}j\left(3\right)\in \left[1,k_4\right],\hfill \\ k_4+5+j\left(3\right)\hfill & \text{if}j\left(3\right)\in \left[k_4+1,k_3\right],\hfill \end{array}\right.$$$$f\left(y_4^{j\left(4\right)}\right)=2k_4+4-2j\left(4\right)\text{if}j\left(4\right)\in \left[1,k_4\right]\text{and}{k}_3>k_4\text{.}$$ Case 3. For $n_1=2k_1-1$, $n_2=2k_2-1$, $n_3=k_3$ and $n_4=k_4$, where $k_i$ is a positive integer for each $i\in \left[1,4\right]$ with $k_1\ge 2$, let $$f\left(x_i\right)=\left\{\begin{array}{cc}2\hfill & \text{if}i=1,\hfill \\ 2k_1+2k_2+k_3+2\hfill & \text{if}i=2,\hfill \\ 2i-5\hfill & \text{if}i\in \left[3,4\right],\hfill \end{array}\right.$$$$f\left(y_1^{j\left(1\right)}\right)=\left\{\begin{array}{cc}0\hfill & \text{if}j\left(1\right)=1,\hfill \\ 3+j\left(1\right)\hfill & \text{if}j\left(1\right)\in \left[2,k_1-1\right],\hfill \\ 2k_2+k_3+2+j\left(1\right)\hfill & \text{if}j\left(1\right)\in \left[k_1,2k_1-1\right],\hfill \end{array}\right.$$$$f\left(y_2^{j\left(2\right)}\right)=\left\{\begin{array}{cc}{k}_1+2+j\left(2\right)\hfill & \text{if}j\left(2\right)\in \left[1,k_2-1\right],\hfill \\ k_1+k_3+2+j\left(2\right)\hfill & \text{if}j\left(2\right)\in \left[k_2,2k_2-1\right],\hfill \end{array}\right.$$$$f\left(y_3^{j\left(3\right)}\right)=\begin{array}{cc}{k}_1+k_2+1+j\left(3\right)\hfill & \text{if}j\left(3\right)\in \left[1,k_3\right],\hfill \end{array}$$$$f\left(y_4^{j\left(4\right)}\right)=\left\{\begin{array}{cc}4\hfill & \text{if}j\left(4\right)=1,\hfill \\ 2k_1+2k_2+k_3+1+j\left(4\right)\hfill & \text{if}j\left(4\right)\in \left[2,k_4\right].\hfill \end{array}\right.$$ Case 4. For $n_1=1$, $n_2=2k_2$, $n_3=2k_3$ and $n_4=k_4$, where $k_i$ is a positive integer for each $i\in \left[2,4\right]$ with $k_4\ge 2$, let $$f\left(x_i\right)=\left\{\begin{array}{cc}2i-2\hfill & \text{if}i\in \left[1,2\right],\hfill \\ 2k_2+2k_3+6\hfill & \text{if}i=3,\hfill \\ 3\hfill & \text{if}i=4,\hfill \end{array}\right.$$$$f\left(y_1^{j\left(1\right)}\right)=\begin{array}{c}{k}_2+k_3+3,\hfill \end{array}$$$$f\left(y_2^{j\left(2\right)}\right)=\left\{\begin{array}{cc}1\hfill & \text{if}j\left(2\right)=1,\hfill \\ 2+j\left(2\right)\hfill & \text{if}j\left(2\right)\in \left[2,k_2\right],\hfill \\ 2k_3+5+j\left(2\right)\hfill & \text{if}j\left(2\right)\in \left[k_2+1,2k_2\right],\hfill \end{array}\right.$$$$f\left(y_3^{j\left(3\right)}\right)=\left\{\begin{array}{cc}\hfill k_2+2+j\left(3\right)\hfill & \hfill \text{if}j\left(3\right)\in \left[1,k_3\right]\text{,}\hfill \\ \hfill k_2+5+j\left(3\right)\hfill & \hfill \text{if}j\left(3\right)\in \left[k_3+1,2k_3\right]\text{,}\hfill \end{array}\right.$$$$f\left(y_4^{j\left(4\right)}\right)=\left\{\begin{array}{cc}{k}_2+k_3+3+j\left(4\right)\hfill & \text{if}j\left(4\right)\in \left[1,2\right],\hfill \\ 2k_2+2k_3+4+j\left(4\right)\hfill & \text{if}j\left(4\right)\in \left[3,k_4\right].\hfill \end{array}\right.$$ Case 5. For $n_1=2k_1-1$, $n_2=2k_2$, $n_3=2k_3$ and $n_4=k_4$, where $k_i$ is a positive integer for each $i\in \left[1,4\right]$ with $k_1\ge 2$, let $$f\left(x_i\right)=\left\{\begin{array}{cc}3-i\hfill & \text{if}i\in \left[1,2\right],\hfill \\ 2k_1+2k_2+2k_3+3\hfill & \text{if}i=3,\hfill \\ 3\hfill & \text{if}i=4,\hfill \end{array}\right.$$$$f\left(y_1^{j\left(1\right)}\right)=\left\{\begin{array}{cc}0\hfill & \text{if}j\left(1\right)=1,\hfill \\ 3+j\left(1\right)\hfill & \text{if}j\left(1\right)\in \left[2,k_1-1\right],\hfill \\ 2k_2+2k_3+3+j\left(1\right)\hfill & \text{if}j\left(1\right)\in \left[k_1,2k_1-1\right],\hfill \end{array}\right.$$$$f\left(y_2^{j\left(2\right)}\right)=\left\{\begin{array}{cc}{k}_1+2+j\left(2\right)\hfill & \text{if}j\left(2\right)\in \left[1,k_2\right],\hfill \\ k_1+2k_3+1+j\left(2\right)\hfill & \text{if}j\left(2\right)\in \left[k_2+1,2k_2\right],\hfill \end{array}\right.$$$$f\left(y_3^{j\left(3\right)}\right)=\left\{\begin{array}{cc}{k}_1+k_2+2+j\left(3\right)\hfill & \text{if}j\left(3\right)\in \left[1,2k_3-1\right],\hfill \\ k_1+2k_2+2k_3+2\hfill & \text{if}j\left(3\right)=2k_3,\hfill \end{array}\right.$$$$f\left(y_4^{j\left(4\right)}\right)=\left\{\begin{array}{cc}4\hfill & \text{if}j\left(4\right)=1,\hfill \\ 2k_1+2k_2+2k_3+2+j\left(4\right)\hfill & \text{if}j\left(4\right)\in \left[2,k_4\right].\hfill \end{array}\right.$$ Therefore, $f$ leads us to conclude that ${\beta }_s\left(G\right)\le n_1+n_2+n_3+n_4+3$ for any positive integers $n_1$, $n_2$, $n_3$ and $n_4$. This completes the proof. □

As a simple consequence of the preceding theorem and Lemma 1, we have the following two results.

Corollary 4

For any positive integers $n_1$,$n_2$,$n_3$ and$n_4$, $$\beta \left(S_{n_1}\cup S_{n_2}\cup S_{n_3}\cup S_{n_4}\right)=n_1+n_2+n_3+n_4+3\text{.}$$

Corollary 5

For any positive integers $n_1$,$n_2$,$n_3$ and$n_4$, $$\mathrm{grac}\left(S_{n_1}\cup S_{n_2}\cup S_{n_3}\cup S_{n_4}\right)=n_1+n_2+n_3+n_4+3\text{.}$$

Applying Theorem 1 together with Corollary 4, we obtain the following result.

Corollary 6

For any positive integers $n_1$,$n_2$,$n_3$ and$n_4$, $$\beta \left(m\left(S_{n_1}\cup S_{n_2}\cup S_{n_3}\cup S_{n_4}\right)\right)=m\left(n_1+n_2+n_3+n_4+4\right)-1\text{,}$$where $m$ is odd.

This result also has rather immediate corollary.

Corollary 7

For any positive integers $n_1$,$n_2$,$n_3$ and$n_4$, $$\mathrm{grac}\left(m\left(S_{n_1}\cup S_{n_2}\cup S_{n_3}\cup S_{n_4}\right)\right)=m\left(n_1+n_2+n_3+n_4+4\right)-1\text{,}$$where $m$ is odd.

5 Conclusions

Our results in this paper ensure that the bounds for the three parameters given in Lemma 1 take the same values. On the other hand, if $G$ is a graceful graph of order $p$ and size $q$, then $${\beta }_s\left(G\right)=\beta \left(G\right)=\mathrm{grac}\left(G\right)=q\ge p-1\text{.}$$However, if $G$ is a forest, then $q<p-1$, and the inequality ${\beta }_s\left(G\right)\ge \beta \left(G\right)$ may be strict as Theorems 3 and 4 indicate. Thus, we propose the following problem.

Problem 1

Find a sufficient condition (in terms of forbidden subgraphs) for a forest $F$ to have ${\beta }_s\left(F\right)=\beta \left(F\right)$.

The inequality $\beta \left(G\right)\ge \mathrm{grac}\left(G\right)$ may be strict when $G$ is a forest. To see this, let $m$ be a positive integer, and define the forest $F\cong m{P}_2$ with $$V\left(F\right)=\left\{x_i:i\in \left[1,m\right]\right\}\cup \left\{y_i:i\in \left[1,m\right]\right\}\text{and}E\left(F\right)=\left\{x_i{y}_i:i\in \left[1,m\right]\right\}\text{.}$$Then the injective function $f:V\left(F\right)\to \left[0,2m-1\right]$ such that $$f\left(x_i\right)=i-1\text{(}i\in \left[1,m\right]\text{) and}f\left(y_i\right)=2m-i\text{(}i\in \left[1,m\right]\text{)}$$provides that $$\left\{|f\left(u\right)-f\left(v\right)|:uv\in E\left(F\right)\right\}=\left\{|f\left(x_i\right)-f\left(y_i\right)|:i\in \left[1,m\right]\right\}=\left\{2\left(m-i\right)+1:i\in \left[1,m\right]\right\}\text{,}$$ which is a set of distinct integers. This implies that $\mathrm{grac}\left(F\right)\le 2m-1$ for every positive integer $m$. This together with Lemma 1 implies that $\mathrm{grac}\left(F\right)=2m-1$ for every positive integer $m$. However, it is known from [5] that if $m\equiv 2(mod4)$, then $\beta \left(F\right)=2m$. From these observations, we arrive at the following problem.

Problem 2

Find a sufficient condition (in terms of forbidden subgraphs) for a forest $F$ to have $\beta \left(F\right)=\mathrm{grac}\left(F\right)$.

We have seen that the inequalities ${\beta }_s\left(G\right)\ge \beta \left(G\right)$ and $\beta \left(G\right)\ge \mathrm{grac}\left(G\right)$ are strict when $G$ is a forest. This leads us to propose the following problem.

Problem 3

Find a sufficient condition (in terms of forbidden subgraphs) for a forest $F$ to have ${\beta }_s\left(F\right)=\beta \left(F\right)=\mathrm{grac}\left(F\right)$.

Finally, the results in this paper and author’s computation of ${\beta }_s\left(S_{n_1}\cup S_{n_2}\right)$ in [7] lead us to propose the following conjecture.

Conjecture 1

For positive integers $n_1$,$n_2$, …,$n_k$, let$G\cong S_{n_1}\cup S_{n_2}\cup \cdots \cup S_{n_k}$. Then $${\beta }_s\left(G\right)=\left\{\begin{array}{cc}m+k-1\hfill & \text{if}{n}_1{n}_2\cdots n_k\text{is even, or}k\equiv 0\text{or}1(mod4),\hfill \\ m+k\hfill & \text{if}{n}_1{n}_2\cdots n_k\text{is odd, and}k\equiv 2\text{or}3(mod4).\hfill \end{array}\right.$$where $m=n_1+n_2+\cdots +n_k$.