On the beta-number of linear forests with an even number of components

Peer review under responsibility of Kalasalingam University.

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,\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.

Keywords:

• Beta-number
• Strong beta-number
• Gracefulness
• Graceful labeling
• Linear forest

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)$. Let $G_1$ and $G_2$ be vertex-disjoint graphs. Then the union of $G_1$ and $G_2$, denoted by $G_1\cup G_2$, is the graph with $V\left(G_1\cup G_2\right)=V\left(G_1\right)\cup V\left(G_2\right)$ and $E\left(G_1\cup G_2\right)=E\left(G_1\right)\cup E\left(G_2\right)$. If $G_1$, $G_2$, …, $G_m$ are pairwise vertex-disjoint graphs that are isomorphic to $G$, then we write $mG$ for $G_1\cup G_2\cup \cdots \cup G_m$. 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 integers.

An important type of graph labeling was introduced by Rosa [1] who called them $\beta$-valuations. 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. The concept of $\alpha$-valuations (a particular type of graceful labeling) was also introduced by Rosa [1] as a tool for decomposing the complete graph into isomorphic subgraphs. A graceful labeling $f$ is called an $\alpha$-valuation if there exists an integer $\lambda$ so that $min\left\{f\left(u\right),f\left(v\right)\right\}\le \lambda <max\{f\left(u\right),f\left(v\right)\}$ for each $uv\in E\left(G\right)$. Graceful labelings and $\alpha$-valuations have been the object of study for many papers. For recent contributions to these subjects 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 defined 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. 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 measure of how close $G$ is to being graceful.

Motivated by the concept of gracefulness, Ichishima et al. [4] defined the beta-number and strong beta-number of a graph. 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$, otherwise. 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)$. Similar to the gracefulness, the (strong) beta-number of a graph $G$ can be regarded as a measure of how close $G$ is to being graceful.

The following lemma found 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{.}$

As usual, a path with $n$ vertices and a star with $n+1$ vertices are denoted by $P_n$ and $S_n$, respectively. A linear forest is a forest for which each component is a path. In the first paper on (strong) beta-numbers of graphs, Ichishima et al. [4] gave some necessary conditions for both of these parameters to be finite and some sufficient conditions for the parameters to be infinite. They also determined the exact values of these parameters for certain classes of graphs including the forests $S_m\cup S_n$ and $P_m\cup S_n$, and proved that every nontrivial tree and forest has finite strong beta-number. In another paper on (strong) beta-numbers of graphs, Ichishima et al. [5] investigated these parameters for forests of the form $m{P}_n$ and $m{S}_n$.

In this paper, we determine a formula for the (strong) beta-number of the linear forests $P_m\cup P_n$. As a corollary of this result, we also provide a partial formula for the beta-number of the disjoint union of multiple copies of the same linear forest.

2 Results on linear forests with an even number of paths

Before presenting formulas for $\beta \left(P_m\cup P_n\right)$ and ${\beta }_s\left(P_m\cup P_n\right)$, we mention the graceful property of paths obtained by Cattell [6].

Theorem 1

Let $v$ be any vertex of the path $P_n$. Then there exists a graceful labeling $f$ of $P_n$ with $f\left(v\right)=i$ for any $i\in \left[1,n-1\right]$ unless $n\equiv 3(mod4)$ or $n\equiv 1(mod12)$; $v$ is in the smaller of the two partite sets of vertices, and $i=\left(n-1\right)∕2$.

With the aid of Theorem 1, Ichishima et al. [5] found the following formulas.

Theorem 2

For every integer $n\ge 2$, $\beta \left(2P_n\right)={\beta }_s\left(2P_n\right)=\left\{\begin{array}{cc}2n\hfill & \text{if}n=2,\hfill \\ 2n-1\hfill & \text{if}n\ge 3.\hfill \end{array}\right.$

With the aid of Theorem 1, it is now possible to extend the preceding result significantly by determining $\beta \left(P_m\cup P_n\right)$ and ${\beta }_s\left(P_m\cup P_n\right)$ for all integers $m$ and $n$ with $2\le m\le n$. Our proof uses the concept of induced subgraph. If $S$ is a nonempty subset of $V\left(G\right)$, then the subgraph $〈S〉$ of $G$ induced by $S$ is the graph with vertex set $S$ and whose edge set consists of those edges of $G$ incident with two elements of $S$. A subgraph $H$ of $G$ is called induced if $H\cong 〈S〉$ for some subset $S$ of $V\left(G\right)$.

Theorem 3

For all integers $m$ and $n$ with $2\le m\le n$, $\beta \left(P_m\cup P_n\right)={\beta }_s\left(P_m\cup P_n\right)=\left\{\begin{array}{cc}m+n\hfill & \text{if}\left(m,n\right)=\left(2,2\right),\hfill \\ m+n-1\hfill & \text{if}\left(m,n\right)\ne \left(2,2\right).\hfill \end{array}\right.$

Proof

In light of the preceding theorem and Lemma 1, it suffices to show that ${\beta }_s\left(P_m\cup P_n\right)\le m+n-1$ for every pair of integers $m$ and $n$ with $m+n\ge 5$ and $n\ge m+1$. For this purpose, let $F\cong P_m\cup P_n$ be the forest with $V\left(F\right)=\left\{x_i:i\in \left[1,m\right]\right\}\cup \left\{y_i:i\in \left[1,n\right]\right\}$and $E\left(F\right)=\left\{x_i{x}_{i+1}:i\in \left[1,m-1\right]\right\}\cup \left\{y_i{y}_{i+1}:i\in \left[1,n-1\right]\right\}\text{,}$and define the induced subgraphs of $F$ as follows. Let $F_1\cong P_m$, $F_2\cong P_{n-1}$ and $F_3\cong P_1$ be the induced subgraphs of $F$ with $V\left(F_1\right)=\left\{x_i:i\in \left[1,m\right]\right\}$, $V\left(F_2\right)=\left\{y_i:i\in \left[1,n-1\right]\right\}$ and $V\left(F_3\right)=\left\{y_n\right\}$. It is well known that every path has an $\alpha$-valuation such that the vertex label of an end-vertex is $0$ (see [1]). It follows that there exists an $\alpha$-valuation $f_1$ of $F_1$ with the property that $f_1\left(x_1\right)=0$. On the other hand, it follows from Theorem 1 that there exists a graceful labeling $f_2$ of $F_2$ with the property that $f_2\left(y_{n-1}\right)=n-⌈m∕2⌉-2$. With these knowledge in hand, consider the vertex labeling $f:V\left(F\right)\to \left[0,m+n-1\right]$ such that $f\left(w\right)=\left\{\begin{array}{cc}1+f_1\left(w\right)\hfill & \text{if}w=x_{2i-1}\text{and}i\in \left[1,⌈m∕2⌉\right],\hfill \\ n+f_1\left(w\right)\hfill & \text{if}w=x_{2i}\text{and}i\in \left[1,⌊m∕2⌋\right],\hfill \\ ⌈m∕2⌉+1+f_2\left(w\right)\hfill & \text{if}w=y_i\text{and}i\in \left[1,n-1\right],\hfill \\ 0\hfill & \text{if}w=y_n.\hfill \end{array}\right.$

To show that $f$ is indeed a bijective function, notice first that $\left\{f_1\left(x_{2i-1}\right):i\in \left[1,⌈m∕2⌉\right]\right\}=\left[0,⌈m∕2⌉-1\right]$and $\left\{f_1\left(x_{2i}\right):i\in \left[1,⌊m∕2⌋\right]\right\}=\left[⌈m∕2⌉,m-1\right]\text{,}$since $f_1$ is an $\alpha$-valuation of $F_1$ with the property that $f_1\left(x_1\right)=0$. This in turn implies that $\left\{f\left(x_{2i-1}\right):i\in \left[1,⌈m∕2⌉\right]\right\}=\left[1,⌈m∕2⌉\right]$and $\left\{f\left(x_{2i}\right):i\in \left[1,⌊m∕2⌋\right]\right\}=\left[⌈m∕2⌉+n,m+n-1\right]\text{.}$Notice also that $\left\{f_2\left(y_i\right):i\in \left[1,n-1\right]\right\}=\left[0,n-2\right]\text{,}$since $f_2$ is a graceful labeling of $F_2$. This implies that $\left\{f\left(y_i\right):i\in \left[1,n-1\right]\right\}=\left[⌈m∕2⌉+1,⌈m∕2⌉+n-1\right]\text{.}$From these observations and the fact that $f\left(y_n\right)=0$, we obtain $\left\{f\left(v\right):v\in V\left(F\right)\right\}=\left[0,m+n-1\right]\text{.}$This indicates that $f$ is a bijective function.

To complete the proof, compute the edge labels given by $|f\left(u\right)-f\left(v\right)|$ for each $uv\in E\left(F\right)$. Since $f_2$ is a graceful labeling of $F_2$, it follows that $\left\{|f_2\left(u\right)-f_2\left(v\right)|:uv\in E\left(F_2\right)\right\}=\left[1,n-2\right]\text{,}$which implies that $\left\{|f\left(u\right)-f\left(v\right)|:uv\in E\left(F_2\right)\right\}=\left[1,n-2\right]\text{.}$Recall that $f_2\left(y_{n-1}\right)=n-⌈m∕2⌉-2$, which implies that $f\left(y_{n-1}\right)=⌈m∕2⌉+1+f_2\left(y_{n-1}\right)=n-1\text{.}$This together with $f\left(y_n\right)=0$ gives $|f\left(y_{n-1}\right)-f\left(y_n\right)|=n-1\text{.}$Since $f_1$ is an $\alpha$-valuation of $F_1$ with the property that $f_1\left(x_1\right)=0$, it follows that if $u\in \left\{f\left(x_{2i}\right):i\in \left[1,⌊m∕2⌋\right]\right\}$ and $v\in \left\{f\left(x_{2i-1}\right):i\in \left[1,⌈m∕2⌉\right]\right\}$, then $f_1\left(u\right)>f_1\left(v\right)$. This implies that $|f\left(u\right)-f\left(v\right)|=n-1+\left(f_1\left(u\right)-f_1\left(v\right)\right)\text{.}$Notice next that $\left\{f_1\left(u\right)-f_1\left(v\right):uv\in E\left(F_1\right)\right\}=\left[1,m-1\right]\text{,}$since $f_1$ is an $\alpha$-valuation of $F_1$ with $f_1\left(x_1\right)=0$. Consequently, $\left\{|f\left(u\right)-f\left(v\right)|:uv\in E\left(F_1\right)\right\}=\left[n,m+n-2\right]\text{.}$It is now immediate that $\left\{|f\left(u\right)-f\left(v\right)|:uv\in E\left(F\right)\right\}=\left[1,E\left(F\right)\right]\text{.}$Therefore, we conclude that ${\beta }_s\left(F\right)\le m+n-1$ for every pair of integers $m$ and $n$ with $m+n\ge 5$ and $n\ge m+1$, completing the proof.

We illustrate the construction described in the preceding theorem with Table 1, which contains the vertex labelings of $F_1$, $F_2$, $F_3$ and $F$ for small values of integers $m$ and $n$.

Table 1 Some vertex labelings of $F_1$, $F_2$, $F_3$ and $F$.

$m$	$n$	$F_1$	$F_2$	$F_3$	$F$
3	4	$(0,2,1)$	$(1,2,0)$	$\left(0\right)$	$(1,6,2),(4,5,3,0)$
3	5	$(0,2,1)$	$(3,0,2,1)$	$\left(0\right)$	$(1,7,2),(6,3,5,4,0)$
3	6	$(0,2,1)$	$(4,0,3,1,2)$	$\left(0\right)$	$(1,8,2),(7,3,6,4,5,0)$
4	5	$(0,3,1,2)$	$(3,0,2,1)$	$\left(0\right)$	$(1,8,2,7),(6,3,5,4,0)$
4	6	$(0,3,1,2)$	$(4,0,3,1,2)$	$\left(0\right)$	$(1,9,2,8),(7,3,6,4,5,0)$
4	7	$(0,3,1,2)$	$(4,1,5,0,2,3)$	$\left(0\right)$	$(1,10,2,9),(7,4,8,3,5,6,0)$

It is known from [5] that $\beta \left(m{P}_2\right)=2m$ if $m\equiv 2(mod4)$, whereas $\beta \left(m{P}_2\right)=2m-1$ in all other cases. In the same paper, it was also shown that 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. These together with Theorem 3 give us the following formula.

Corollary 1

For every pair of integers $m$, $n_1$ and $n_2$ such that $m$ is odd and $2\le n_1\le n_2$, $\beta \left(m\left(P_{n_1}\cup P_{n_2}\right)\right)=\left\{\begin{array}{cc}m\left(n_1+n_2\right)\hfill & \text{if}\left(n_1,n_2\right)=\left(2,2\right),\hfill \\ m\left(n_1+n_2\right)-1\hfill & \text{if}\left(n_1,n_2\right)\ne \left(2,2\right).\hfill \end{array}\right.$

It was conjectured by Ichishima et al. [5] that the (strong) beta-number of a forest of order $p$ is either $p-1$ or $p$. Note that our results in this paper add credence to this conjecture.

Notes

Peer review under responsibility of Kalasalingam University.