On the strength of some trees

Abstract

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.

Keywords:

• Strength
• Caterpillar
• Tree
• Graph labeling
• Corona

1 Introduction

In this paper, we will consider only finite graphs without loops or multiple edges. We refer the reader to the book by Chartrand and Lesniak [1] for graph-theoretical notation and terminology not described in this paper. The graph with $n$ vertices and no edges is referred to as the empty graph of order $n$ and is denoted by $n{K}_1$. The $\mathit{degree}$ $\mathit{of}$ a vertex $v$ in a graph is number of edges of $G$ incident with $v$ and is denoted by ${deg}_{G}v$. A vertex of degree $0$ is called an isolated vertex and a vertex of degree $1$ is an end-vertex of $G$. The minimum degree of $G$ is the minimum degree among the vertices of $G$ and is denoted by $\delta \left(G\right)$.

For the sake of notational convenience, we will denote the interval of integers $k$ such that $i\le k\le j$ by simply writing $\left[i,j\right]$.

For a graph $G$ of order $p$ and size $q$, a bijective function $f:V\left(G\right)\cup E\left(G\right)\to \left[1,p+q\right]$ is called an edge-magic labeling if $f\left(u\right)+f\left(v\right)+f\left(uv\right)$ is a constant $c\left(f\right)$ (called the magic constant) for each $uv\in E\left(G\right)$. If such a labeling exists, then $G$ is called an edge-magic graph.

The notion of edge-magic labelings was first introduced in 1970 by Kotzig and Rosa [2]. These labelings were originally called “magic valuations” by them. These were rediscovered in 1996 by Ringel and Lladó [3] who coined one of the now popular terms for them: edge-magic labelings. Afterwards, Enomoto et al. [4] defined a slightly restricted version of an edge-magic labeling $f$ of a graph $G$ by requiring that $f\left(V\left(G\right)\right)=\left[1,\left|V\left(G\right)\right|\right]$. Such a labeling was called by them super edge-magic . Thus, a super edge-magic graph is a graph that admits a super edge-magic labeling. It is worth to mention that Acharya and Hegde [5] had already discovered such graphs in 1991 under the name of “strongly indexable graphs”. However, they arrived at this concept from a different point view. Their motivation is much clear from the following alternative definition found in [6].

Lemma 1

A graph $G$ of order $p$ and size $q$ is super edge-magic if and only if there exists a bijective function $f:V\left(G\right)\to \left[1,p\right]$ such that the set $$S=\left\{f\left(u\right)+f\left(v\right)\left|uv\in E\left(G\right)\right.\right\}$$ consists of $q$ consecutive integers. In such a case, $f$ extends to a super edge-magic labeling of $G$ with magic constant $k=p+q+s$ , where $s=min\left(S\right)$ and $$S=\left[k-\left(p+q\right),k-\left(p+1\right)\right]\text{.}$$

The concept of super magic strength was introduced by Avadayappan et al. [7]. The super magic strength $sm\left(G\right)$ of a graph $G$ is defined as the minimum of all magic constants $c\left(f\right)$, where the minimum is taken over all super edge-magic labelings $f$ of $G$, that is, $$sm\left(G\right)=min\left\{c\left(f\right)\left|f\text{is a super edge-magic labeling of}G\right.\right\}\text{.}$$It is an immediate consequence of the definition that if $G$ is not a super edge-magic graph or an empty graph, then $sm\left(G\right)$ is undefined (or we could define $sm\left(G\right)=+\infty$). It is also true that $G$ is a super edge-magic graph if and only if $sm\left(G\right)<+\infty$.

As the concept of super magic strength is effectively defined only for super edge-magic graphs, this concept was generalized in [8] for any nonempty graph as follows. A numbering $f$ of a graph $G$ of order $p$ is a labeling that assigns distinct elements of the set $\left[1,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,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{.}$$A numbering $f$ of a graph $G$ for which ${\mathrm{str}}_f\left(G\right)=\mathrm{str}\left(G\right)$ is called a strength labeling of $G$. If $G$ is an empty graph, then $\mathrm{str}\left(G\right)$ is undefined (or we could define $\mathrm{str}\left(G\right)=+\infty$).

There are several sharp bounds for the strength of a graph in terms of well-known invariants in graph theory (see [8]). Among others, the following result that provides a lower bound for $\mathrm{str}\left(G\right)$ in terms of the order and the minimum degree is particularly useful.

Lemma 2

For every graph $G$ of order $p$ with $\delta \left(G\right)\ge 1$ , $$\mathrm{str}\left(G\right)\ge p+\delta \left(G\right)\text{.}$$

The following results were obtained in [8] for the paths $P_n$ and stars $K_{1,n-1}$ of order $n$. These classes of graphs illustrate the sharpness of the bound given in Lemma 2.

Theorem 1

For every integer $n\ge 2$ , $$\mathrm{str}\left(P_n\right)=n+1\text{.}$$

Theorem 2

For every integer $n\ge 2$ , $$\mathrm{str}\left(K_{1,n-1}\right)=n+1\text{.}$$

We close this section with suggestions for further reading. A survey article on graph labelings and related topics can be found in Gallian [9], and a book by Bača and Miller [10] is another useful resource. Readers interested in more information on super edge-magic graphs should consult the books by López and Muntaner-Batle [11] as well as Marr and Wallis [12], which also include information on other kinds of graph labelings.

2 The strength of Caterpillars

In this section, we investigate the strength of caterpillars, beginning with double stars. The double star $S_{m,n}$ is a tree obtained by joining the centers of two disjoint stars $K_{1,m}$ and $K_{1,n}$ with an edge.

Theorem 3

For every two positive integers $m$ and $n$ , $$\mathrm{str}\left(S_{m,n}\right)=m+n+3\text{.}$$

Proof

The inequality $\mathrm{str}\left(S_{m,n}\right)\ge m+n+3$ is a direct consequence of Lemma 2. In order to verify the inequality in the other direction, it suffices to find a numbering $f$ of $S_{m,n}$ with ${\mathrm{str}}_f\left(S_{m,n}\right)=m+n+3$. Assume, without loss of generality, that $1\le m\le n$, and define the double star $S_{m,n}$ with $$V\left(S_{m,n}\right)=\left\{x,y\right\}\cup \left\{x_i\left|i\in \left[1,m\right]\right.\right\}\cup \left\{y_i\left|i\in \left[1,n\right]\right.\right\}$$and $$E\left(S_{m,n}\right)=\left\{xy\right\}\cup \left\{x{x}_i\left|i\in \left[1,m\right]\right.\right\}\cup \left\{y{y}_i\left|i\in \left[1,n\right]\right.\right\}\text{.}$$Now, consider the labeling $f:V\left(S_{m,n}\right)\to \left[1,m+n+2\right]$ such that $f\left(x\right)=1$, $f\left(y\right)=2$, $$f\left(v\right)=\left\{\begin{array}{cc}i+n+2\hfill & \text{if}v=x_i\text{and}i\in \left[1,m\right],\hfill \\ i+2\hfill & \text{if}v=y_i\text{and}i\in \left[1,n\right].\hfill \end{array}\right.$$Notice that $f$ assigns distinct elements of the set $\left[1,m+n+2\right]$ to the vertices of $S_{m,n}$. Also, notice that $$\left\{f\left(x\right)+f\left(y\right)\right\}=\left\{3\right\}\text{,}$$$$\left\{f\left(x\right)+f\left(x_i\right)\left|i\in \left[1,m\right]\right.\right\}=\left[n+4,m+n+3\right]\text{,}$$$$\left\{f\left(y\right)+f\left(y_i\right)\left|i\in \left[1,n\right]\right.\right\}=\left[5,n+4\right]\text{.}$$ Thus, $f$ has the property that $${\mathrm{str}}_f\left(S_{m,n}\right)=max\left\{f\left(u\right)+f\left(v\right)\left|uv\in E\left(S_{m,n}\right)\right.\right\}=f\left(x\right)+f\left(x_m\right)=m+n+3\text{.}$$ Consequently, $\mathrm{str}\left(S_{m,n}\right)=m+n+3$. □

A caterpillar is a tree $T$ with the property that the removal of the end-vertices of $T$ results in a path. This path is referred to as the spine of the caterpillar. If the spine is trivial, the caterpillar is a star; if the spine is $K_2$, then the caterpillar is a double star. The next result includes caterpillars whose spine is both trivial and $K_2$. Realize that the way of defining the spine provided in the proof is intended to make the vertex labeling easy to describe.

Theorem 4

For every caterpillar $T$ of order $p$ , $$\mathrm{str}\left(T\right)=p+1\text{.}$$

Proof

In light of Theorems 2 and 3, it suffices to prove the theorem for caterpillars whose spine contains at least $3$ vertices and both end-vertices of the spine have end-vertices attached. The lower bound for $\mathrm{str}\left(T\right)$ is obtained immediately from Lemma 2.

To establish the upper bound for $\mathrm{str}\left(T\right)$, let $T$ be the caterpillar with $$V\left(T\right)=\left\{u_i\left|i\in \left[1,m\right]\right.\right\}\cup \left(\bigcup _{i=1}^m\left\{v_i^j|j\in \left[1,n_i\right]\right\}\right)$$and $$E\left(T\right)=\left\{u_i{u}_{i+1}\left|i\in \left[1,m-1\right]\right.\right\}\cup \left(\bigcup _{i=1}^m\left\{u_i{v}_i^j|j\in \left[1,n_i\right]\right\}\right)\text{.}$$Then $T$ has the spine $S$ with $V\left(S\right)=\left\{u_i\left|i\in \left[1,m\right]\right.\right\}$ and $$E\left(S\right)=\left\{u_i{u}_{i+1}\left|i\in \left[1,m-1\right]\right.\right\}\text{.}$$Note that if we define a permutation $\pi$ of $V\left(S\right)$ by $$\pi \left(u_i\right)=x_j\left(i\in \left[1,m\right]\text{and}j\in \left[1,m\right]\right)\text{,}$$where $n_j^{\prime }={deg}_T{u}_i-{deg}_S{u}_i=n_i$ with $n_1^{\prime }\ge n_2^{\prime }\ge \cdots \ge n_m^{\prime }$, then $\pi$ is an involutive automorphism of $S$, and we have $V\left(S\right)=\left\{x_i\left|i\in \left[1,m\right]\right.\right\}$. Hence, every edge of $S$ joins vertices $x_s$ and $x_t$ with $j=i+1$ and $i\in \left[1,m-1\right]$ whenever $${\pi }^{-1}\left(x_s\right)=u_j\text{and}{\pi }^{-1}\left(x_t\right)=u_i$$or $${\pi }^{-1}\left(x_s\right)=u_i\text{and}{\pi }^{-1}\left(x_t\right)=u_j\text{.}$$In the case that $n_s=n_t$ with $1\le s<t\le m$, we may assume that $\pi \left(u_s\right)$ is located to the left of $\pi \left(u_t\right)$ in the drawing of $T$ in the plane.

The preceding construction allows us to define the caterpillar $T$ with $$V\left(T\right)=\left\{x_i\left|i\in \left[1,m\right]\right.\right\}\cup \left(\bigcup _{i=1}^m\left\{y_i^j|j\in \left[1,n_i^{\prime }\right]\right\}\right)$$and $$E\left(T\right)=\left\{x_s{x}_t\left|{\pi }^{-1}\left(x_s\right){\pi }^{-1}\left(x_t\right)\in E\left(S\right)\right.\right\}\cup \left(\bigcup _{i=1}^m\left\{x_i{y}_i^j|j\in \left[1,n_i^{\prime }\right]\right\}\right)\text{.}$$If we let ${\sigma }_i={\sum }_{k=1}^i{n}_k^{\prime }$, then $p=m+{\sigma }_m$. Notice that if $n_i^{\prime }=0$ for some $i\in \left[1,m\right]$, then we treat $\left[1,n_i^{\prime }\right]$ as the empty set. Thus, assume that $n_i^{\prime }\ne 0$ for some $i\in \left[1,m\right]$; otherwise, $S\cong P_m$ and the result follows from Theorem 1. It remains to show the existence of a numbering $f$ of $T$ for which ${\mathrm{str}}_f\left(T\right)=p+1$. To complete this, there are two cases to proceed according to the possible values for the integer $m$.

Case 1: Assume that $m\le ⌊p∕2⌋$, and consider the labeling $f:V\left(T\right)\to \left[1,p\right]$ such that $$f\left(v\right)=\left\{\begin{array}{cc}i\hfill & \text{if}v=x_i\text{and}i\in \left[1,m\right],\hfill \\ p-{\sigma }_i+j\hfill & \text{if}v=y_i^j,i\in \left[1,m\right]\text{and}j\in \left[1,n_i^{\prime }\right].\hfill \end{array}\right.$$Then $f$ assigns distinct elements of the set $\left[1,p\right]$ to the vertices of $T$. In particular, $f$ assigns distinct elements of the set $\left[1,m\right]$ to the vertices of $S$. This implies that $$max\left\{f\left(u\right)+f\left(v\right)\left|uv\in E\left(S\right)\right.\right\}\le m+\left(m-1\right)=2m-1\le 2⌊p∕2⌋-1<p\text{.}$$ However, $$max\left\{f\left(u\right)+f\left(v\right)\left|uv\in E\left(T\right)\setminus E\left(S\right)\right.\right\}=max{E}_{ij}\text{,}$$where $E_{ij}=\left\{p-{\sigma }_i+i+j\left|i\in \left[1,m\right]\text{and}j\in \left[1,n_i^{\prime }\right]\right.\right\}$. At this point, let $i$ be the integer so that $n_i^{\prime }\ne 0$ with $i\in \left[1,m\right]$. Then $n_1^{\prime }\ge n_2^{\prime }\ge \cdots \ge n_i^{\prime }\ge 1$, which implies that ${\sigma }_{i-1}\ge i-1$. Thus, $$max\left\{f\left(u\right)+f\left(v\right)\left|uv\in E\left(T\right)\setminus E\left(S\right)\right.\right\}\le max{E}_{ij}\le p-{\sigma }_i+i+n_i^{\prime }=p-{\sigma }_{i-1}+i\le p-\left(i-1\right)+i=p+1\text{.}$$ Consequently, $$max\left\{f\left(u\right)+f\left(v\right)\left|uv\in E\left(T\right)\right.\right\}\le p+1\text{,}$$so $f$ has the property that ${\mathrm{str}}_f\left(T\right)=p+1$.

Case 2: Assume that $m\ge ⌊p∕2⌋+1$, and let $l=|\left\{n_i^{\prime }\left|i\in \left[1,m\right]\text{and}{n}_i^{\prime }=0\right.\right\}|$. Then $n_i^{\prime }\ge 1$ for $i\in \left[1,m-l\right]$ and $n_i^{\prime }=0$ for $i\in \left[m-l+1,m\right]$. With this knowledge in hand, consider the labeling $f:V\left(T\right)\to \left[1,p\right]$ such that $$f\left(v\right)=\left\{\begin{array}{cc}i\hfill & \text{if}v=x_i\text{and}i\in \left[1,m-l\right],\hfill \\ m+1-i\hfill & \text{if}v=x_{m-l-1+2i}\text{and}i\in \left[1,⌈l∕2⌉\right],\hfill \\ m-l+i\hfill & \text{if}v=x_{m-l+2i}\text{and}i\in \left[1,⌊l∕2⌋\right],\hfill \\ p-{\sigma }_i+j\hfill & \text{if}v=y_i^j,i\in \left[1,m-l\right]\text{and}j\in \left[1,n_i^{\prime }\right].\hfill \end{array}\right.$$Then $f$ assigns distinct elements of the set $\left[1,p\right]$ to the vertices of $T$. Thereby, $f$ assigns distinct elements of the set $\left[1,m\right]$ to the vertices of $S$ as follows: $$\left\{f\left(x_i\right)\left|i\in \left[1,m-l\right]\right.\right\}=\left[1,m-l\right]\text{,}$$$$\left\{f\left(x_{m-l-1+2i}\right)\left|i\in \left[1,⌈l∕2⌉\right]\right.\right\}=\left[m-⌈l∕2⌉+1,m\right]\text{,}$$$$\left\{f\left(x_{m-l+2i}\right)\left|i\in \left[1,⌊l∕2⌋\right]\right.\right\}=\left[m-l+1,m-⌈l∕2⌉\right]\text{.}$$

For the rest of the proof, we will examine the induced edge labels given by $f\left(u\right)+f\left(v\right)$ for each $uv\in E\left(T\right)$. Then, in a similar manner to Case 1, we have $$max\left\{f\left(u\right)+f\left(v\right)\left|uv\in E\left(T\right)\setminus E\left(S\right)\right.\right\}\le max{E}_{ij}\le p-{\sigma }_i+i+n_i^{\prime }=p-{\sigma }_{i-1}+i\le p-\left(i-1\right)+i=p+1\text{,}$$ where $E_{ij}=\left\{p-{\sigma }_i+i+j\left|i\in \left[1,m-l\right]\text{and}j\in \left[1,n_i^{\prime }\right]\right.\right\}$. However, there are three subcases to pursue according to the possibility for the edge $x_s{x}_t\in E\left(S\right)$.

Subcase 2.1: Let $W_1=\left\{x_s{x}_t\in E\left(S\right)\left|n_s^{\prime }\ne 0\text{and}{n}_t^{\prime }\ne 0\right.\right\}$. Then $$max\left\{f\left(u\right)+f\left(v\right)\left|uv\in W_1\right.\right\}=f\left(x_{m-l-1}\right)+f\left(x_{m-l}\right)=\left(m-l-1\right)+\left(m-l\right)=2m-2l-1\text{.}$$ However, since $T$ has $\left(p-m\right)$ end-vertices and $\left(m-l\right)$ vertices of $S$ have end-vertices, it follows that $p-m\ge m-l$, that is, (1) $$l\ge 2m-p\text{.}$$(1) This implies that (2) $$2m-2l-1\le 2p-2m-1\text{.}$$(2) Since $m\ge ⌊p∕2⌋+1$, it also follows from (2) that (3) $$2p-2m-1\le 2p-2⌊p∕2⌋-3\text{.}$$(3) Thus, the fact that $2⌊p∕2⌋\ge p-1$ together with (3) implies that $$max\left\{f\left(u\right)+f\left(v\right)\left|uv\in W_1\right.\right\}\le 2p-2⌊p∕2⌋-3\le p-2\text{.}$$

Subcase 2.2: Let $W_2=\left\{x_s{x}_t\in E\left(S\right)\left|n_s^{\prime }\ne 0\text{and}{n}_t^{\prime }=0\right.\right\}$. Then $$max\left\{f\left(u\right)+f\left(v\right)\left|uv\in W_2\right.\right\}=f\left(v_{m-l}\right)+f\left(v_{m-l+1}\right)=\left(m-l\right)+m=2m-l\text{.}$$ Thus, it follows from (1) that $$max\left\{f\left(u\right)+f\left(v\right)\left|uv\in W_2\right.\right\}\le 2m-l\le 2m-\left(2m-p\right)=p\text{.}$$

Subcase 2.3: Let $W_3=\left\{x_s{x}_t\in E\left(S\right)\left|n_s^{\prime }=0\text{and}{n}_t^{\prime }=0\right.\right\}$. Then $$max\left\{f\left(u\right)+f\left(v\right)\left|uv\in W_3\right.\right\}=f\left(x_{m-l-1+2i}\right)+f\left(x_{m-l+2i}\right)=\left(m-l+i\right)+\left(m+1-i\right)=2m-l+1$$ for each $i\in \left[1,⌊l∕2⌋\right]$. Thus, it follows from (1) that $$max\left\{f\left(u\right)+f\left(v\right)\left|uv\in W_3\right.\right\}\le 2m-l+1\le 2m-\left(2m-p\right)+1=p+1\text{.}$$ Consequently, $$max\left\{f\left(u\right)+f\left(v\right)\left|uv\in E\left(T\right)\right.\right\}\le p+1\text{,}$$so $f$ has the property that ${\mathrm{str}}_f\left(T\right)=p+1$. □

3 The strength of complete $n$-ary trees

The $k$ -level complete $n$ -ary tree $T_{n,k}$ is a tree in which the $i$th level consists of $n^{i-1}$ vertices and each vertex in level $i<k$ has $n$ ‘sons’ at level $i+1$. If $n=2$, then $T_{n,k}$ is referred to as a $k$ -level complete binary tree. The strength of $T_{2,k}$ depends on $k$ as the next result indicates. The proof involves the concept of distance in a graph. For a connected graph $G$ and pair $u$, $v\in V\left(G\right)$, the distance $d\left(u,v\right)$ between $u$ and $v$ is the length of a shortest $u-v$ path in $G$.

Theorem 5

For every integer $k\ge 2$ , $$\mathrm{str}\left(T_{2,k}\right)=2^k\text{.}$$

Proof

The lower bound for $\mathrm{str}\left(T_{2,k}\right)$ follows immediately from Lemma 2, since $\left|V\left(T_{2,k}\right)\right|=2^k-1$ and $\delta \left(T_{2,k}\right)=1$.

To establish the upper bound for $\mathrm{str}\left(T_{2,k}\right)$, it suffices to show the existence of a numbering $f$ of $T_{2,k}$ for which ${\mathrm{str}}_f\left(T_{2,k}\right)=2^k$. Let $T_{2,k}$ be given as a rooted tree in the plane. Then $T_{2,k}$ has a unique vertex of degree $2$, so chose this distinct vertex to be the root of $T_{2,k}$ and denoted it by $r$. Of course, if $T_{2,k}$ is drawn in the plane, then by letting $$S_i=\left\{v\in V\left(T_{2,k}\right)\left|i=d\left(r,v\right)+1\right.\right\}\text{,}$$the vertices in each level $i\ge 2$ can be ordered from left to right using the integers $1,2,\dots ,\left|S_i\right|$. Since the $i$th level consists of $2^i$ vertices, it follows that $\left|S_i\right|=2^{i-1}$. Thus, $S_i$ can be written as $$S_i=\left\{v_i^j|j\in \left[1,2^{i-1}\right]\right\}\text{,}$$where $i$ represents the level that the vertex occupies in $T_{2,k}$ and $j$ represents the place that the vertex in level $i$ occupies in the level starting to count from left to right. If we let $$E_i=\left\{uv\in E\left(T_{2,k}\right)\left|u\in S_i\text{and}v\in S_{i+1}\right.\right\}\text{,}$$then $\left|E_i\right|=2^i$ and the edges of $E_i$ can also be ordered from left to right in ascending order starting with $1$ and ending up with $2^i$ for each set $E_i$. Thus, we will write $e_i^j$ for the edge in the set $E_i$ that occupies position $j$ when counting the edges of $E_i$ from left to right. This implies that if $e_i^j,e_i^l\in E_i$ with $j<l$, then $e_i^j$ is located to the left of $e_i^l$ in the drawing of $T_{2,k}$ in the plane.

Since $T_{2,2}\cong P_3$, it follows from Theorem 1 that $\mathrm{str}\left(T_{2,2}\right)=2^2$. It also follows from Theorem 4 that $\mathrm{str}\left(T_{2,3}\right)=2^3$, since $T_{2,3}$ is a caterpillar. Let $k$ be an integer with $k\ge 4$, and consider the labeling $f:V\left(T_{2,k}\right)\to \left[1,2^k-1\right]$ such that $$f\left(v_i^j\right)=\left\{\begin{array}{cc}{2}^{k-1}-2^i+j\hfill & \text{if}i\in \left[1,k-2\right]\text{and}j\in \left[1,2^{i-1}\right],\hfill \\ 2^{k-2}+1-j\hfill & \text{if}i=k-1\text{and}j\in \left[1,2^{k-2}\right],\hfill \\ 2^{k-1}-1+j\hfill & \text{if}i=k\text{and}j\in \left[1,2^{k-1}\right].\hfill \end{array}\right.$$This implies that $$\left\{f\left(v\right)\left|v\in S_{k-1}\right.\right\}=\left[1,2^{k-2}\right]\text{,}$$$$\left\{f\left(v\right)\left|v\in S_i\text{and}i\in \left[1,k-2\right]\right.\right\}=\left[2^{k-2}+1,2^{k-1}-1\right]\text{,}$$$$\left\{f\left(v\right)\left|v\in S_k\right.\right\}=\left[2^{k-1},2^k-1\right]\text{.}$$ Since ${\sum }_{i=1}^k\left|S_i\right|=2^k-1$, it follows that $f$ assigns distinct elements of the set $\left[1,2^k-1\right]$ to the vertices of $T_{2,k}$.

For each $e_i^j=uv\in E\left(T_{2,k}\right)$, where $u\in S_i$ and $v\in S_{i+1}$, we write $f\left(e_i^j\right)$ for the induced edge label given by $f\left(u\right)+f\left(v\right)$. Notice then that for each $j,l\in \left[1,2^{i-1}\right]$ with $j<l$, we have $f\left(e_i^j\right)\le f\left(e_i^l\right)$ if $i\in \left[1,k-1\right]$ with $i\ne k-2$, whereas we have $f\left(e_i^j\right)\ge f\left(e_i^l\right)$ if $i=k-2$. Thus, $f$ has the property that $$max\left\{f\left(\underset{i}{\overset{j}{e}}\right)|i\in \left[1,k-2\right]\text{and}j\in \left[1,2^{i-1}\right]\right\}=max\left\{f\left(\underset{1}{\overset{1}{v}}\right)+f\left(\underset{2}{\overset{2}{v}}\right),f\left(\underset{k-2}{\overset{1}{v}}\right)+f\left(\underset{k-1}{\overset{1}{v}}\right)\right\}=f\left(v_1^1\right)+f\left(v_2^2\right)=\left(2^{k-1}-1\right)+\left(2^{k-1}-2\right)=2^k-3$$ and $$max\left\{f\left(\underset{k-1}{\overset{j}{e}}\right)|j\in \left[1,2^{i-1}\right]\right\}=f\left(v_{k-1}^{2^{k-2}}\right)+f\left(v_k^{2^{k-1}}\right)=1+\left(2^{k-1}-1+2^{k-1}\right)=2^k\text{,}$$ implying that $${\mathrm{str}}_f\left(T_{2,k}\right)=max\left\{f\left(u\right)+f\left(v\right)\left|uv\in E\left(T_{2,k}\right)\right.\right\}=2^k\text{.}$$Consequently, $\mathrm{str}\left(T_{2,k}\right)=2^k$. □

The strength of $T_{n,k}$ is also determined by considering a drawing of $T_{n,k}$ as a rooted tree in the plane; the proof is quite similar to that of Theorem 5 and will not be included.

Theorem 6

For every two integers $n\ge 2$ and $k\ge 2$ , $$\mathrm{str}\left(T_{n,k}\right)=\frac{n^k-1}{n-1}+1\text{.}$$

4 The strength of the corona of graphs

The corona of two graphs was introduced by Frucht and Harary [13]. The corona $G\odot H$ of two graphs $G$ and $H$ is defined as the graph obtained by taking one copy of $G$ (which has order $p$) and $p$ copies of $H$, and then joining the $i$th vertex of $G$ to every vertex in the $i$th copy of $H$. It is now possible to present the following result.

Theorem 7

Let $G$ be a graph of order $p$ with $\delta \left(G\right)\ge 1$ . If $\mathrm{str}\left(G\right)=p+\delta \left(G\right)$ , then $$\mathrm{str}\left(G\odot n{K}_1\right)=\left(n+1\right)p+1$$ for every positive integer $n$ .

Proof

Suppose that $G$ is a graph of order $p$ with $\delta \left(G\right)\ge 1$, and let $f$ be a strength labeling of $G$ with $\mathrm{str}\left(G\right)=p+\delta \left(G\right)$. Assume that $f$ has the property that $f\left(v_i\right)=i$ for each $i\in \left[1,p\right]$, where $V\left(G\right)=\left\{v_i\left|i\in \left[1,p\right]\right.\right\}$. Further, let $H\cong G\odot n{K}_1$, and define the graph $H$ with $$V\left(H\right)=V\left(G\right)\cup \left\{w_i^j|i\in \left[1,p\right]\text{and}j\in \left[1,n\right]\right\}$$and $$E\left(H\right)=E\left(G\right)\cup \left\{v_i{w}_i^j|i\in \left[1,p\right]\text{and}j\in \left[1,n\right]\right\}\text{.}$$Then $\left|V\left(H\right)\right|=\left(n+1\right)p$ and $\delta \left(H\right)=1$. Thus, the lower bound for $\mathrm{str}\left(H\right)$ follows from Lemma 2.

To establish the upper bound for $\mathrm{str}\left(H\right)$, consider the labeling $g:V\left(H\right)\to \left[1,\left(n+1\right)p\right]$ such that $$g\left(x\right)=\left\{\begin{array}{cc}i\hfill & \text{if}x=v_i\text{and}i\in \left[1,p\right],\hfill \\ \left(n+1\right)p-ni+j\hfill & \text{if}x=w_i^j,i\in \left[1,p\right]\text{and}j\in \left[1,n\right].\hfill \end{array}\right.$$Then $\left\{g\left(v_i\right)\left|i\in \left[1,p\right]\right.\right\}=\left[1,p\right]$ and $$\left\{g\left(w_i^j\right)|i\in \left[1,p\right]\text{and}j\in \left[1,n\right]\right\}=\left[p+1,\left(n+1\right)p\right]\text{.}$$This implies that $g$ assigns distinct elements of the set $\left[1,\left(n+1\right)p\right]$ to the vertices of $H$. It is now immediate that $$p+\delta \left(G\right)\le p+\left(p-1\right)=2p-1<\left(n+1\right)p+1$$ for every positive integer $n$. Moreover, $g$ has the property that $${\mathrm{str}}_g\left(H\right)=max\left\{g\left(u\right)+g\left(v\right)\left|uv\in E\left(H\right)\right.\right\}=g\left(w_1^n\right)+g\left(v_1\right)=\left(n+1\right)p+1\text{.}$$ Consequently, $\mathrm{str}\left(H\right)=\left(n+1\right)p+1$. □

The preceding result is of particular interest, since there are infinitely many graphs $G$ for which $\mathrm{str}\left(G\right)=\left|V\left(G\right)\right|+\delta \left(G\right)$ (see [8] for a detailed list of graphs). Applying it with such classes of graphs repeatedly, we obtain other classes of graphs $H$ for which $\mathrm{str}\left(H\right)=\left|V\left(H\right)\right|+1$ again.

5 Conclusions

In this paper, we have shown that every caterpillar and $k$-level complete $n$-ary tree attains the bound provided in Lemma 2. We have also established a formula for the strength of the corona of certain graphs and an arbitrary number of isolated vertices (see Theorem 7). A new tree can be created by taking the corona with isolated vertices. Therefore, applying Theorem 7 with the classes of trees studied in this paper, we obtain other classes of trees $T$ for which $\mathrm{str}\left(T\right)=\left|V\left(T\right)\right|+1$. These trees include a class of lobsters (a lobster is a tree $T$ with the property that the removal of the end-vertices of $T$ results in a caterpillar). This motivates us to propose the following problem.

Problem 1

For every lobster $T$, determine the exact value of $\mathrm{str}\left(T\right)$.