Rikio Ichishima^a , Francesc A Muntaner-Batle^b , Akito Oshima^b

^aDepartment of Sport and Physical Education, Faculty of Physical Education, Kokushikan University, 7-3-1 Nagayama, Tama-shi, Tokyo 206-8515, Japan ^bGraph Theory and Applications Research Group, School of Electrical Engineering and Computer Science, Faculty of Engineering and Built Environment, The University of Newcastle, NSW 2308 Australia

ichishim@kokushikan.ac.jp, famb1es@yahoo.es, akitoism@yahoo.co.jp

A bipartite graph G with partite sets X and Y is called consecutively super edge-magic if there exists a bijective function f : V (G) ∪ E (G) → {1, 2, . . . , |V (G)| + |E (G)|} with the property that f (X) = {1, 2, . . . , |X|}, f (Y ) = {|X| + 1, |X| + 2, . . . , |V (G)|} and f (u)+f (v)+f (uv) is constant for each uv ∈ E (G). The question studied in this paper is for which bipartite graphs it is possible to add a finite number of isolated vertices so that the resulting graph is consecutively super edge-magic. If it is possible for a bipartite graph G, then we say that the minimum such number of isolated vertices is the consecutively super edge-magic deficiency of G; otherwise, we define it to be +∞. This paper also includes a detailed discussion of other concepts that are closely related to the consecutively super edge-magic deficiency.

Keywords: consecutively super edge-magic labeling, super edge-magic labeling, consecutively super edge-magic deficiency, super edge-magic deficiency, alpha-number, beta-number

Mathematics Subject Classification : 05C78; 05C05, 05C76, 90C27

DOI: 10.5614/ejgta.2020.8.1.6

1. Introduction

We generally follow the notation and terminology pertaining to graphs of [5]. All graphs considered here are finite, simple and undirected. We will denote the set of vertices and edges of a graph G by V (G) and E (G), respectively. For two graphs G¹ and G² with disjoint vertex sets,

Received: 19 February 2019, Revised: 1 November 2019, Accepted: 14 November 2019.

the union \(G \cong G_1 \cup G_2\) has \(V(G) = V(G_1) \cup V(G_2)\) and \(E(G) = E(G_1) \cup E(G_2)\). If a graph G consists of m disjoint copies of a graph H, then we write \(G \cong mH\). For integers a and b with \(a \leq b\), we will denote the set \(\{x \in \mathbb{Z} : a \leq x \leq b\}\) by writing [a,b], where \(\mathbb{Z}\) denotes the set of all integers.

In a seminal paper published in 1970, Kotzig and Rosa [21] introduced the notion of edge-magic labelings. These labelings were originally called magic valuations by them. These were rediscovered in 1996 by Ringel and Lladó [28] who coined one of the now popular terms for them: edge-magic labelings. More recently, they have also been referred to as edge-magic total labelings by Wallis [30]. For a graph G, a bijective function \(f:V(G)\cup E(G)\to [1,|V(G)|+|E(G)|]\) is called an edge-magic labeling if f(u)+f(v)+f(uv) is a constant (called the valence) for each \(uv\in E(G)\). If such a labeling exists, then G is called an edge-magic graph. In 1998, Enomoto et al. [6] defined a slightly restricted version of an edge-magic labeling f of a graph G by requiring that f(V(G))=[1,|V(G)|]. Such a labeling was called by them a super edge-magic labeling. Thus, a super edge-magic graph is a graph that admits a super edge-magic labeling.

It is worth mentioning that Acharya and Hegde [1] had introduced the concept of strongly indexable graph. It turns out that the concepts of strongly indexable graph and super edge-magic graph are equivalent. Lately, super edge-magic labelings and super edge-magic graphs have been called by Wallis [30] strong edge-magic total labelings and strongly edge-magic graphs, respectively. Moreover, according to the latest version of the survey on graph labelings by Gallian [13] available to the authors, Hegde and Shetty [15] showed that the properties of being super edge-magic and strongly k-indexable (see [13] for the definition) are equivalent.

In 2001, Muntaner-Batle [24] introduced the concept of special super edge-magic labeling of a bipartite graph. Let G be a bipartite graph with partite sets X and Y. If G has a super edge-magic labeling f with the property that f(X) = [1, |X|] and f(Y) = [|X| + 1, |V(G)|], then f is called a special super edge-magic labeling. Oshima [26] subsequently called such labelings consecutively super edge-magic. In this paper, we prefer to use the latter terminology to emphasize the property that a consecutively super edge-magic labeling uses consecutive integers in each partite set. We also refer a bipartite graph with a consecutively super edge-magic labeling as a consecutively super edge-magic graph.

The following lemma found in [24] is particularly useful in showing that dense bipartite graphs are not consecutively super edge-magic.

Lemma 1.1. If G is a consecutively super edge-magic graph, then

\[\left| E\left( G\right) \right| \leq \left| V\left( G\right) \right| -1.\]

The following lemma found in [24] provides us with a necessary and sufficient condition for a bipartite graph to be consecutively super edge-magic.

Lemma 1.2. Let G be a bipartite graph with partite sets X and Y. Then G is consecutively super edge-magic if and only if there exists a bijective function \(f:V(G)\to [1,|V(G)|]\) such that f(X)=[1,|X|], f(Y)=[|X|+1,|V(G)|] and the set

\[\{f(u) + f(v) : uv \in E(G)\}\]

consists of |E(G)| consecutive integers.

For every graph G, Kotzig and Rosa [21] proved that there exists an edge-magic graph H such that H ∼= G ∪ nK¹ for some nonnegative integer n. This motivated them to define the edge-magic deficiency. The edge-magic deficiency µ(G) of a graph G is the smallest nonnegative integer n for which G ∪ nK¹ is edge-magic. Inspired by Kotzig-Rosa notion, Figueroa-Centeno et al. [11] defined the concept of super edge-magic deficiency µs(G) of a graph G to be either the smallest nonnegative integer n with the property that G ∪ nK¹ is super edge-magic or +∞ if there exists no such integer n. If G is a graph with µs(G) = 0, then G is super edge-magic. Thus, the super edge-magic deficiency of a graph G is a measure of how close G is to being super edge-magic.

Kotzig and Rosa [21] found an upper bound for the edge-magic deficiency of a graph of order p, namely, µ(G) ≤ Fp+2 − 2 − p+1 2 , where F^p is the p-th term of the Fibonacci sequence. This implies that every graph has finite edge-magic deficiency. However, not all graphs have finite super edge-magic deficiency. In order to see this, it suffices to consider the following lemma taken from [11].

Lemma 1.3. If G is a graph such that the degrees of all vertices are even and |E (G)| ≡ 2 (mod 4), then µ^s (G) = +∞.

We now provide the definition for a parameter introduced in [27], the consecutively super edgemagic deficiency, used to measure the closeness of a graph to be consecutively super edge-magic. The consecutively super edge-magic deficiency µc(G) of a graph G is defined to be either the smallest nonnegative integer n with the property that G ∪ nK¹ is consecutively super edge-magic or +∞ if there exists no such integer n.

As an immediate consequence of the above three definitions, we have the following relations taking place among three parameters.

Lemma 1.4. For every graph G,

\[\mu\left(G\right) \leq \mu_{s}\left(G\right) \leq \mu_{c}\left(G\right).\]

For a thorough study of graph labeling problems, see the survey by Gallian [13]. For more information on super edge-magic graphs and related topics, see the books by Baca and Miller [2], ˇ Lopez and Muntaner-Batle [22] and Marr and Wallis [23]. ´

We end this introduction by summarizing the work conducted in this paper. In Section 2, we introduced some additional concepts (called the alpha-number and strong alpha-number), and supply relations among these parameters and the consecutively super edge-magic deficiency. In Section 3, we show that if a graph G admits a consecutively super edge-magic labeling and m is odd, then mG admits a consecutively super edge-magic labeling, and we provide an explicit formula for a consecutively super edge-magic labeling of mG. This result allows us to construct infinite families of consecutively super edge-magic graphs using a single graph as a seed. In addition, we present results concerning the consecutively super edge-magic deficiency of the union of graphs. In particular, we show that if G¹ and G² are two graphs with µ^c (G1) ≤ µ^c (G2) < +∞, then µ^c (G¹ ∪ G2) < +∞. Moreover, we give some results on the alpha-number of the union of graphs. In Section 4, we compute the consecutively super edge-magic deficiency and (strong) alpha-number for some classes of forests. In Section 5, we provide a brief discussion of forests regarding to the parameters studied in this paper or in the past, and propose new conjectures on the consecutively super edge-magic deficiency of forests.

2. Relations Among Parameters

We start with some necessary definitions for presenting our results included in this section.

The graph labeling method that has received the most attention over the years was originated with a paper by Rosa [29] in 1967 who called them β-valuations. A few years later, Golomb [14] called these labelings graceful and this is the term that has been used since then. For a graph G, an injective function f : V (G) → [0, |E (G)|] is called a graceful labeling if each uv ∈ E(G) is labeled |f(u) − f(v)| and the resulting edge labels are distinct. Rosa [29] also introduced the concept of α-valuations (a particular type of graceful labelings) as a tool for decomposing the complete graph into isomorphic subgraphs. A graceful labeling f is called an α-valuation if there exists an integer λ so that min {f(u), f(v)} ≤ λ < max{f(u), f(v)} for each uv ∈ E(G). Rosa [29] pointed out that a graph that admits an α-valuation is necessarily bipartite and therefore cannot contain a cycle of odd length.

It has demonstrated in [18] that α-valuations are sometimes useful for computing the super edge-magic deficiency of certain graphs. In particular, they proved that if G is a graph without isolated vertices that has an α-valuation, then µ^s (G) ≤ |E (G)|−|V (G)|+ 1. This bound is sharp in the sense that there are infinitely many graphs G for which µ^s (G) = |E (G)| − |V (G)| + 1. Indeed, all complete bipartite graphs (see [7]) and some 2-regular bipartite graphs (see [10, 11, 18, 19]) attain the bound.

The gracefulness grac(G) of a graph G is the smallest positive integer n for which there exists an injective function f : V (G) → [0, n] such that each uv ∈ E (G) is labeled |f (u) − f (v)| and the resulting set of edge labels consists of distinct integers. It is easy to see that grac(G) ≤ 2 ^p−¹−1 for every graph G of order p. This implies that every graph has finite gracefulness. If G is a graph of size q with grac(G) = q, then G is graceful. Thus, the gracefulness of a graph G is a measure of how close G is to being graceful. This definition first appeared in a paper by Golomb [14]. For further knowledge on the gracefulness of graphs, the authors suggest that the reader consults the results in [3, 20].

The concept of gracefulness motivated the authors to define the beta-number and strong betanumber in [17]. The beta-number β (G) of a graph G is the smallest positive integer n for which there exists an injective function f : V (G) → [0, n] such that each uv ∈ E (G) is labeled |f (u) − f (v)| and the resulting set of edge labels is [c, c + |E (G)| − 1] for some positive integer c. The beta-number of G is +∞, otherwise. If c = 1, then the resulting beta-number is called the strong beta-number of G and it is denoted by β^s (G). It is clear that if G is a graph with β (G) = |E (G)|, then G is graceful. It is also true that if G is a graph with β^s (G) = |E (G)|, then G is graceful. Thus, the beta-number and strong beta-number of a graph G are measures of how close G is to being graceful.

We now provide the definitions for a new type of parameter (called the alpha-number) introduced in [27] and its restriction. They play an important role in the study of consecutively super edge-magic deficiency. The alpha-number α (G) of a graph G is defined to be the smallest positive integer n such that β (G) = n with the additional property that there exists an integer λ so that min {f(u), f(v)} ≤ λ < max{f(u), f(v)} for each uv ∈ E(G). The alpha-number is defined to be +∞, otherwise. If c = 1, then the resulting alpha-number is called the strong alpha-number of G and it is denoted by α^s (G). These parameters can be regarded as measures of how close a graph

is to having an α-valuation.

The four parameters described in this section make up a string of inequalities as the following lemma indicates.

Lemma 2.1. For every graph G of order p and size q,

\[\max \{p-1, q\} \le \operatorname{grac}(G) \le \beta(G) \le \alpha(G) \le \alpha_s(G).\]

With the above definitions in hand, we can now state the following result established in [27], which shows the connection between the alpha-number of a graph and its consecutively super edge-magic deficiency.

Theorem 2.1. If G is a graph of order p, then

\[\alpha\left(G\right) = \mu_{c}\left(G\right) + p - 1.\]

The preceding theorem indicates that the problems of determining the alpha-number and the consecutively super edge-magic deficiency are in fact equivalent. It is also immediate from the same result that for any graph G, α (G) = +∞ if and only if µ^c (G) = +∞.

The following corollary gives us an inequality relating the strong alpha-number of a graph and its consecutively super edge-magic deficiency. This result is easily obtained by substituting c = 1 into the equation c = x + n + p − q − s + 2 given in the proof of Theorem 2.1 (see [27]).

Corollary 2.1. Assume that a graph G∪nK¹ has a consecutively super edge-magic labeling f for which µ^c (G) = n. If G ∪ nK¹ has the partite sets X and Y such that n = |E (G)| − |V (G)| − |X| + s − 1, where s = min {f (u) + f (v) : uv ∈ E (G)}, then

\[\alpha_s(G) \le \mu_c(G) + |V(G)| - 1.\]

It is worth mentioning that the bound presented in Corollary 2.1 is sharp (for instance, see Corollary 4.4 in Section 4).

If G is a graph with an α-valuation, then it is clear that α (G) = |E (G)|. In this case, this fact together with Theorem 2.1 gives us an exact formula for the consecutively super edge-magic deficiency of such graphs in terms of its order and size.

Corollary 2.2. If G is a graph with an α-valuation, then

\[\mu_{c}\left(G\right)=\left|E\left(G\right)\right|-\left|V\left(G\right)\right|+1.\]

The above corollary is relatively important, since various classes of graphs have been proved to admit α-valuations (see [13] for a detailed list of results).

3. Results on Unions of Graphs

In their investigation of (super) edge-magic properties of disconnected graphs, Figueroa-Centeno et al. [11] proved that if G is a (super) edge-magic bipartite or tripartite graph, then mG is (super) edge-magic when m is odd. In the following theorem, we present a consecutively super edge-magic analogue of the mentioned result.

Theorem 3.1. If G is a consecutively super edge-magic graph and m is odd, then mG is consecutively super edge-magic.

Proof. Without loss of generality, assume that m is odd and m ≥ 3. Since G is a consecutively super edge-magic graph, it follows that G is bipartite. Thus, if we let U and V denote the two partite sets of G, then we have E (G) = UV , where the juxtaposition of two partite sets denotes the edges between those two sets. Take f : V (G) → [1, |V (G)|] to be an arbitrary consecutively super edge-magic labeling of G, and define H ∼= mG to be the graph with

\[V\left(H\right) = \bigcup_{i=1}^{m} \left(U_{i} \cup V_{i}\right) \text{ and } E\left(G\right) = \bigcup_{i=1}^{m} U_{i}V_{i},\]

where xⁱ ∈ Xⁱ for each i ∈ [1, m] if and only if x ∈ X (X is one of the sets U or V ). Now, consider the vertex labeling g : V (H) → [1, m |V (G)|] such that

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Then g extends to a consecutively super edge-magic labeling of H with valence ms−3 (m − 1) /2+ m |V (G) ∪ E (G)|, where s = min {f (u) + f (v) : uv ∈ E (G)}. To show this, notice first that

\[g\left(U\right)=\left[1,m\left|U\right|\right] \text{ and } g\left(V\right)=\left[m\left|U\right|+1,m\left|V\left(G\right)\right|\right],\]

since

\[f\left(U\right)=\left[1,\left|U\right|\right] \text{ and } f\left(V\right)=\left[\left|U\right|+1,\left|V\left(G\right)\right|\right].\]

Next, to see that g (u) + g (v) + g (uv) = ms − 3 (m − 1) /2 + m |V (G) ∪ E (G)| for every uv ∈ E (H), where u ∈ U and v ∈ V , notice that if we let c = ms − 3 (m − 1) /2, then we have

\[\{g(u) + g(v) : uv \in E(H)\} = [c, c + |E(H)| - 1].\]

Therefore, we conclude by means of Lemma 1.2 that mG is consecutively super edge-magic when m is odd and m ≥ 3.

It is interesting to notice that Theorem 3.1 can be deduced from the results found in [12] with relative ease. However, the proof given in this paper provides us with an explicit formula for the consecutively super edge-magic labeling announced in the statement of Theorem 3.1.

The preceding theorem also yields the following corollary.

Corollary 3.1. If G is a bipartite graph and m is odd, then µ^c (mG) ≤ mµ^c (G).

Proof. Let G be a bipartite graph and let m be odd. Also, assume that µ^c (G) < +∞, otherwise the result is trivial. Then G ∪ nK¹ is consecutively super edge-magic for some nonnegative integer n. Since G∪nK¹ is certainly bipartite, it follows from Theorem 3.1 that m (G ∪ nK1) ∼= mG∪mnK¹ is consecutively super edge-magic, which implies that µ^c (mG) ≤ mµ^c (G).

The following result is an immediate consequence of Theorem 2.1 and Corollary 3.1.

Corollary 3.2. If G is a bipartite graph and m is odd, then

\[\alpha \left( mG \right) \le m\alpha \left( G \right) + m - 1.\]

For a nontrivial tree that has an α-valuation, we have the following result.

Corollary 3.3. If T is a nontrivial tree of order p that has an α-valuation, then

\[\alpha\left(mT\right)=mp-1,\]

where m is odd.

Proof. Let T be a nontrivial tree of order p that has an α-valuation, and assume that m is odd. Then α (T) = |E (T)| = p − 1. This together with Corollary 3.2 implies that α (mT) ≤ mp − 1. On the other hand, the reverse inequality quickly follows from Lemma 2.1.

The following result is easily obtained from Corollary 3.2 and Lemma 2.1.

Corollary 3.4. If F is a forest of order p such that α (F) = p − 1, then

\[\alpha\left(mF\right) = mp - 1,\]

where m is odd.

The union of two graphs with finite super edge-magic deficiency does not always have finite super edge-magic deficiency. In fact, the cycle C³ of length 3 is clearly super edge-magic, but we can see from Lemma 1.3 that µ^s (2C3) = +∞. However, if two graphs are both consecutively super edge-magic, the situation is different as the next theorem indicates.

Theorem 3.2. If G¹ and G² are consecutively super edge-magic graphs, then

\[\mu_c\left(G_1\cup G_2\right)<+\infty.\]

Proof. Assume that G¹ and G² are consecutively super edge-magic graphs. For each i ∈ [1, 2], let Xⁱ and Yⁱ be the partite sets of Gⁱ , where |Xⁱ | = xⁱ and |Yⁱ | = yⁱ , and let fⁱ be a consecutively super edge-magic labeling of Gⁱ . Now, without loss of generality, assume that fⁱ has the property that xⁱ ≥ yⁱ for each i ∈ [1, 2]. Otherwise, take a consecutively super edge-magic labeling gⁱ given by

\[g_i(v) = x_i + y_i + 1 - f_i(v),\]

where v ∈ Xi∪Yⁱ and i ∈ [1, 2]. Moreover, assume that f¹ and f² have the property that 2x¹ +2 ≥ s¹ and s2+|E (G2)|−1 ≥ x2+y2+1, respectively, where sⁱ = min {fⁱ (u) + fⁱ (v) : uv ∈ E (Gi)} and i ∈ [1, 2]. Otherwise, take a consecutively super edge-magic labeling gⁱ given by

\[g_i(v) = x_i + 1 - f_i(v) \text{ if } v \in X_i\]

and

\[g_i(v) = 2x_i + y_i + 1 - f_i(v) \text{ if } v \in Y_i\]

for each i ∈ [1, 2].

With the above properties of f¹ and f² in hand, consider the function f such that

\[f(v) = \begin{cases} f_1(v) & \text{if } v \in X_1, \\ f_1(v) + s_2 - s_1 + 2x_1 + |E(G_2)| & \text{if } v \in Y_1, \\ f_2(v) + x_1 & \text{if } v \in X_2 \cup Y_2. \end{cases}\]

Then f extends to a consecutively super edge-magic labeling of G¹ ∪ G² ∪ nK¹ for some nonnegative integer n. To show this, notice first that

\[f_i(X_i) = \{j : j \in [1, x_i]\} \text{ and } f_i(Y_i) = \{j : j \in [x_i + 1, x_i + y_i]\}\]

for each i ∈ [1, 2]. This implies that

\[\{f(v): v \in X_1\} = [1, x_1],\] \[\{f(v): v \in X_2\} = [x_1 + 1, x_1 + x_2],\] \[\{f(v): v \in Y_2\} = [x_1 + x_2 + 1, x_1 + x_2 + y_2],\] \[\{f(v): v \in Y_1\} = [s_2 - s_1 + 3x_1 + |E(G_2)| + 1, s_2 - s_1 + 3x_1 + |E(G_2)| + y_1].\]

Next, to see that f is an injective function, notice that

\[s_2 - s_1 + 3x_1 + |E(G_2)| + 1 \ge x_1 + x_2 + y_2 + 1.\]

This is true as we indicate next, since f¹ and f² have the aforementioned properties.

\[s_{2} - s_{1} + 3x_{1} + |E(G_{2})| + 1 - (x_{1} + x_{2} + y_{2} + 1)\] \[= s_{2} - s_{1} + 2x_{1} + |E(G_{2})| - x_{2} - y_{2}\] \[= (s_{2} + |E(G_{2})| - 1) + 1 - x_{2} - y_{2} - s_{1} + 2x_{1}\] \[\geq (x_{2} + y_{2} + 1) + 1 - x_{2} - y_{2} - s_{1} + 2x_{1}\] \[= 2x_{1} + 2 - s_{1}\] \[\geq s_{1} - s_{1} = 0.\]

Finally, notice that the set

\[\{f(u) + f(v) : uv \in E(G_1 \cup G_2)\}\]

consists of |E (G¹ ∪ G2)| consecutive integers, since

\[\{f_1(u) + f_1(v) : uv \in E(G_1)\} = [s_1, s_1 + |E(G_1)| - 1],\]
\(\{f_2(u) + f_2(v) : uv \in E(G_2)\} = [s_2, s_2 + |E(G_2)| - 1]\)

and

\[f(u) + f(v) = \begin{cases} f_1(u) + f_1(v) + s_2 - s_1 + 2x_1 + |E(G_2)| & \text{if } uv \in E(G_1), \\ f_2(u) + f_2(v) + 2x_1 & \text{if } uv \in E(G_2). \end{cases}\]

As an immediate consequence of Theorems 2.1 and 3.2, we have the following result.

Corollary 3.5. If G¹ and G² are two graphs such that α (G1) = |V (G1)| − 1 and α (G2) = |V (G2)| − 1, then α (G¹ ∪ G2) < +∞.

Theorem 3.2 yields the following corollary as well.

Corollary 3.6. If G¹ and G² are two graphs such that µ^c (G1) ≤ µ^c (G2) < +∞, then

\[\mu_c\left(G_1\cup G_2\right)<+\infty.\]

Proof. Assume that G¹ and G² are two graphs such that µ^c (G1) ≤ µ^c (G2) < +∞. Then there exists some nonnegative integers m and n such that G¹ ∪ mK¹ and G² ∪ nK¹ are consecutively super edge-magic. It follows from Theorem 3.2 that µ^c (G¹ ∪ G² ∪ (m + n) K1) < +∞, which implies that µ^c (G¹ ∪ G2) < +∞.

Combining Theorem 2.1 with Corollary 3.6, we obtain the following result.

Corollary 3.7. If G¹ and G² are two graphs such that α (G1) ≤ α (G2) < +∞, then

\[\alpha\left(G_1\cup G_2\right)<+\infty.\]

4. Results on Forests

In their 2006 paper, Figueroa-Centeno et al. [11] provided a constructive proof that nontrivial trees and forests have finite super edge-magic deficiencies. In fact, they have verified those facts by showing the stronger statement that nontrivial trees and forests have finite consecutively super edge-magic deficiencies. In light of Theorem 2.1, this implies that nontrivial trees and forests have finite alpha-numbers. In a series of papers [8, 9, 11], Figueroa-Centeno et al. studied the super edge-magic properties of forests. Afterwards, they conjectured in [10] that µ^s (F) ≤ 1 for every forest F with two components. In this section, we present some consecutively super edgemagic deficiency and (strong) alpha-number analogues of the super edge-magic deficiency results on forests found in [10, 11].

Theorem 4.1. For every positive integer m,

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Proof. It is straightforward that P² is a consecutively super edge-magic graph. It follows from Theorem 3.1 that the forest mP² is consecutively super edge-magic when m is odd. This implies that µ^c (mP2) = 0 when m is odd.

Now, recall that Kotzig and Rosa [21] proved that the forest mP² is super edge-magic if and only if m is odd. This implies that µ^s (mP2) ≥ 1 when m is even. This together with Lemma 1.4 implies that µ^c (mP2) ≥ 1 when m is even. To establish the reverse inequality, define the forest F ∼= mP² ∪ K¹ with

\[V\left(F\right) = \left\{x_{i} : i \in [1, m]\right\} \cup \left\{y_{i} : i \in [1, m]\right\} \cup \left\{z\right\} \text{ and } E\left(F\right) = \left\{x_{i} y_{i} : i \in [1, m]\right\},\]

and consider the vertex labeling f : V (F) → [1, 2m + 1] such that

\[f(w) = \begin{cases} i & \text{if } w = x_i \text{ and } i \in [1, m], \\ 3m/2 + 1 + i & \text{if } w = y_i \text{ and } i \in [1, m/2], \\ m/2 + i & \text{if } w = y_i \text{ and } i \in [m/2 + 1, m], \\ 3m/2 + 1 & \text{if } w = z. \end{cases}\]

It follows from Lemma 1.2 that f extends to a consecutively super edge-magic labeling of F with valence 9m/2 + 3. To show this, notice first that the two partite sets of the vertex labels in F are {f (xi) : i ∈ [1, m]} = [1, m] and

\[{f(y_i): i \in [1, m]} \cup {z} = [m+1, 2m+1].\]

Next, to see that f (u) + f (v) + f (uv) = 9m/2 + 3 for all uv ∈ E (F), notice that

\[{f(u) + f(v) : uv \in E(F)} = [3m/2 + 2, 5m/2 + 1]\]

or, equivalently,

\[{f(u) + f(v) : uv \in E(F)} = [s, s + |E(F)| - 1],\]

where s = 3m/2 + 2. Consequently, we conclude that µ^c (F) ≤ 1 when m is even, completing the proof.

For every positive integer m, it is known from [16] that β (mP2) = 2m when m ≡ 2 (mod 4) and β (mP2) = 2m − 1 in all other cases. By letting G ∼= mP² in Theorem 2.1, we now obtain the following result from Theorem 4.1.

Corollary 4.1. For every positive integer m,

\[\alpha(mP_2) = \begin{cases} 2m - 1 & \text{if } m \text{ is odd,} \\ 2m & \text{if } m \text{ is even.} \end{cases}\]

We next present a formula for the strong alpha-number of the forest mP2.

Theorem 4.2. For every positive integer m,

\[\alpha_s(mP_2) = \begin{cases} 2m-1 & \text{if } m=1, \\ +\infty & \text{if } m \neq 1. \end{cases}\]

Proof. The result is trivial for m = 1. Thus, assume that m ≥ 2 and suppose, to the contrary, that α^s (mP2) = n for some positive integer n. Then there exists an injective function f : V (mP2) → [0, n] such that {|f (x) − f (y)| : xy ∈ E (mP2)} = [1, m]and there exists an integer λ so that min {f (x), f (y)} ≤ λ < max {f (x), f (y)} for each xy ∈ E (mP2). It follows that such a λ must be the smaller of the two vertex labels that yield the edge labeled 1. Let k¹ be the second largest vertex label in the smaller of the two partite sets of mP2. On the other hand, let k² be the second smallest vertex label in the larger of the two partite sets of mP2. Then we have k¹ ≤ λ − 1 and k² ≥ λ + 2. This implies that k² − k¹ ≥ 3, that is, the second smallest edge label is at least 3. Consequently, 2 ∈ {| / f (x) − f (y)| : xy ∈ E (mP2)}, which contradicts the fact that 2 ∈ {|f (x) − f (y)| : xy ∈ E (mP2)}. Therefore, we conclude that α^s (mP2) = +∞ for all m ≥ 2.

The preceding theorem indicates that extending the range of vertex labels of a forest does not need to produce a finite strong alpha-number. This is unexpected in light of the aforementioned fact that every forest has a finite alpha-number (see beginning of this section).

We next present a result on forests that consist of two disjoint copies of a star. For this purpose, let S^m denote the star with m + 1 vertices.

Theorem 4.3. For every two positive integers m and n, µ^c (S^m ∪ Sn) = 1.

Proof. First, we show that µ^c (S^m ∪ Sn) ≤ 1 for every two positive integers m and n. To do this, define the forest F¹ ∼= S^m ∪ Sⁿ ∪ K¹ with

\[V(F_1) = \{x, y, z\} \cup \{x_i : i \in [1, m]\} \cup \{y_i : i \in [1, n]\}\]

and

\[E(F_1) = \{xx_i : i \in [1, m]\} \cup \{yy_i : i \in [1, n]\},\\]

and consider the vertex labeling f : V (F1) → [1, m + n + 3] such that

\[f(w) = \begin{cases} 2 & \text{if } w = x, \\ 1 & \text{if } w = y, \\ 2+i & \text{if } w = x_i \text{ and } i \in [1, m], \\ m+3 & \text{if } w = z, \\ m+3+i & \text{if } w = y_i \text{ and } i \in [1, n]. \end{cases}\]

It follows from Lemma 1.2 that f extends to a consecutively super edge-magic labeling of F¹ with valence m + n + 4. To show this, notice first that the two partite sets of the vertex labels in F¹ are {f (x), f (y)} = [1, 2] and

\[\{f(x_i): i \in [1, m]\} \cup \{f(y_i): i \in [1, m]\} \cup \{f(z)\} = [3, m + n + 3].\]

Next, to see that f (u) + f (v) + f (uv) = m + n + 4 for all uv ∈ E (F1), notice that

\[{f(u) + f(v) : uv \in E(F_1)} = [5, m + n + 4]\]

or, equivalently,

\[\{f(u) + f(v) : uv \in E(F_1)\} = [5, 5 + |E(F_1)| - 1].\]

This indicates that µ^c (F1) ≤ 1 for every two positive integers m and n.

To verify the inequality in the other direction, let F² ∼= S^m ∪ Sⁿ be the forest with

\[V(F_2) = \{x, y\} \cup \{x_i : i \in [1, m]\} \cup \{y_i : i \in [1, n]\}\]

and

\[E(F_2) = \{xx_i : i \in [1, m]\} \cup \{yy_i : i \in [1, n]\},\]

and suppose, to the contrary, that F² has a consecutively super edge-magic labeling f. Then there are two cases to concern with the possibilities of partite sets of F2.

Case 1. The sets A = {xⁱ : i ∈ [1, m]} ∪ {y} and B = {x} ∪ {yⁱ : i ∈ [1, n]} form the partite sets of F2.

Case 2. The sets A = {x, y} and B = {xⁱ : i ∈ [1, m]} ∪ {yⁱ : i ∈ [1, n]} form the partite sets of F2.

According to the vertex labels of each partite set of F2, each of Cases 1 and 2 divides into two subcases as indicate next.

Subcase 1-1. The set of vertex labels of each partite set of F² is

\[f(A) = [1, m+1]\] and \(f(B) = [m+2, m+n+2]\).

Subcase 1-2. The set of vertex labels of each partite set of F² is

\[f(A) = [n+2, m+n+2]\] and \(f(B) = [1, n+1]\).

Subcase 2-1. The set of vertex labels of each partite set of F² is

\[f(A) = [1, 2]\] and \(f(B) = [3, m + n + 2]\).

Subcase 2-2. The set of vertex labels of each partite set of F² is

\[f(A) = [m+n+1, m+n+2]\] and \(f(B) = [1, m+n]\).

Furthermore, according to the induced edge labels of F2, each of Subcases 1-1 and 1-2 in turn divides into two subcases as indicate next.

Subcase 1-1-1. The set of induced edge labels of F² is

\[{f(u) + f(v) : uv \in E(F_2)} = [m+3, 2m+n+2].\]

Subcase 1-1-2. The set of induced edge labels of F is

\[\{f(u) + f(v) : uv \in E(F_2)\} = [m+4, 2m+n+3].\]

Subcase 1-2-1. The set of induced edge labels of F² is

\[\{f(u) + f(v) : uv \in E(F_2)\} = [n+4, m+2n+3].\]

Subcase 1-2-2. The set of induced edge labels of F² is

\[{f(u) + f(v) : uv \in E(F_2)} = [n+3, m+2n+2].\]

Similarly, according to the induced edge labels of F2, each of Subcases 2-1 and 2-2 in turn divides into two subcases as indicate next.

Subcase 2-1-1. The set of induced edge labels of F² is

\[{f(u) + f(v) : uv \in E(F_2)} = [4, m + n + 3].\]

Subcase 2-1-2. The set of induced edge labels of F² is

\[{f(u) + f(v) : uv \in E(F_2)} = [5, m + n + 4].\]

Subcase 2-2-1. The set of induced edge labels of F² is

\[\{f(u) + f(v) : uv \in E(F_2)\} = [m + n + 3, 2m + 2n + 2].\]

Subcase 2-2-2. The set of induced edge labels of F² is

\[\{f(u) + f(v) : uv \in E(F_2)\} = [m + n + 2, 2m + 2n + 1].\]

Subcases 1-1-1, 1-1-2, 1-2-1 and 1-2-2 hold the following claim.

Claim 1. If one of Subcases 1-1-1, 1-1-2, 1-2-1 or 1-2-2 is satisfied, then all of these subcases are satisfied.

Fist of all, we show that if Subcase 1-1-1 is true, then so is Subcase 1-1-2. To see this, define the vertex labeling g such that

\[g(v) = \begin{cases} m+2-f(v) & \text{if } v \in A, \\ 2m+n+4-f(v) & \text{if } v \in B. \end{cases}\]

Then g extends to a consecutively super edge-magic labeling of F² such that

\[g(A) = [1, m+1]\] and \(g(B) = [m+2, m+n+2]\),

producing that

\[\{g(u) + g(v) : uv \in E(F_2)\} = [m+4, 2m+n+3].\]

Next, to see that Subcase 1-1-1 implies Subcase 1-2-1, define the vertex labeling g such that

\[g\left(v\right) = m + n + 3 - f\left(v\right)\]

for all v ∈ A ∪ B. Then g extends to a consecutively super edge-magic labeling of F² such that

\[g(A) = [n+2, m+n+2]\] and \(g(B) = [1, n+1]\),

producing that

\[\{g(u) + g(v) : uv \in E(F_2)\} = [n+4, m+2n+3].\]

Finally, to see that Subcase 1-1-1 implies Subcase 1-2-2, define the vertex labeling g such that

\[g(v) = \begin{cases} f(v) + n + 1 & \text{if } v \in A, \\ f(v) - m - 1 & \text{if } v \in B. \end{cases}\]

Then g extends to a consecutively super edge-magic labeling of F² such that

\[g(A) = [n+2, m+n+2]\] and \(g(B) = [1, n+1]\),

producing that

\[\{g(u) + g(v) : uv \in E(F_2)\} = [n+3, m+2n+2].\]

Conversely, if one of Subcases 1-1-2, 1-2-1 or 1-2-2 is satisfied, then Subcase 1-1-1 is satisfied by the aforementioned vertex labelings g. This completes the proof of Claim 1.

Subcases 2-1-1, 2-1-2, 2-2-1 and 2-2-2 hold the following claim.

Claim 2. If one of Subcases 2-1-1, 2-1-2, 2-2-1 or 2-2-2 is satisfied, then all of these subcases are satisfied.

First of all, we show that if Subcase 2-1-1 is true, then so is Subcase 2-1-2. To see this, define the vertex labeling g such that

\[g(v) = \begin{cases} 3 - f(v) & \text{if } v \in A, \\ m + n + 5 - f(v) & \text{if } v \in B. \end{cases}\]

Then g extends to a consecutively super edge-magic labeling of F² such that

\[g(A) = [1, 2] \text{ and } g(B) = [3, m + n + 2],\]

producing that

\[\{g(u) + g(v) : uv \in E(F_2)\} = [5, m + n + 4].\]

Next, to see that Subcase 2-1-1 implies Subcase 2-2-1, define the vertex labeling g such that

\[g\left(v\right) = m + n + 3 - f\left(v\right)\]

for all v ∈ A ∪ B. Then g extends to a consecutively super edge-magic labeling of F² such that

\[g(A) = [m+n+1, m+n+2]\] and \(g(B) = [1, m+n]\),

producing that

\[\{g(u) + g(v) : uv \in E(F_2)\} = [m + n + 3, 2m + 2n + 2].\]

Finally, to see that Subcase 2-1-1 implies Subcase 2-2-2, define the vertex labeling g such that

\[g(v) = \begin{cases} f(v) + m + n & \text{if } v \in A, \\ f(v) - 2 & \text{if } v \in B. \end{cases}\]

Then g extends to a consecutively super edge-magic labeling of F² such that

\[g(A) = [m+n+1, m+n+2]\] and \(g(B) = [1, m+n]\),

producing that

\[\{g(u) + g(v) : uv \in E(F_2)\} = [m + n + 2, 2m + 2n + 1].\]

Conversely, if one of Subcases 2-1-2, 2-2-1 or 2-2-2 is satisfied, then Subcase 2-1-1 is satisfied by the aforementioned vertex labelings g. This completes the proof of Claim 2.

The logically equivalent contrapositive of Claim 2 states that if one of Subcases 1-1-1, 1-1-2, 1-2-1 or 1-2-2 is not satisfied, then all of these subcases are not satisfied. Thus, we particularly show the following claim.

Claim 3. Subcase 1-1-1 is not satisfied.

First, assume that f (y) = 1. Then f (x) 6= m + 2, and the sum of the induced edge labels of F² is

\[\sum_{uv \in E(F_2)} (f(u) + f(v)) = \sum_{i=m+3}^{2m+n+2} i = \frac{(m+n)(3m+n+5)}{2}.\]

Since deg v = 1 for all v ∈ F² − {x, y}, the sum of the vertex labels of F² is

\[\sum_{v \in V(F_2)} f(v) = \sum_{i=1}^{m+n+2} i = \frac{(m+n+2)(m+n+3)}{2}.\]

Our assumption together with the fact that

\[\sum_{uv \in E(F_2)} (f(u) + f(v)) = \sum_{v \in V(F_2)} f(v) + (m-1) f(x) + (n-1) f(y)\]

implies that m² + mn − n − 2 = (m − 1) f (x). Let h (m) = m² + mn − n − 2. To satisfy the last equation with the property that f (x) is a positive integer, it is necessary that h (1) = 0; however, h (1) = −1. Thus, Claim 3 is true when f (y) = 1.

Next, assume that f (x) = m + 2. Then f (y) 6= 1, and our assumption and the fact that

\[\sum_{uv \in E(F_2)} (f(u) + f(v)) = \sum_{v \in V(F_2)} f(v) + (m-1) f(x) + (n-1) f(y)\]

implies that mn−m−1 = (n − 1) f (y). Let h 0 (n) = mn−m−1. To satisfy the last equation with the property that f (y) is a positive integer, it is necessary that h 0 (1) = 0; however, h 0 (1) = −1. Thus, Claim 3 is true when f (x) = m + 2. Hence, Claim 3 is established by the preceding arguments.

The logically equivalent contrapositive of Claim 2 states that if one of Subcases 2-1-1, 2-1-2, 2-2-1 or 2-2-2 is not satisfied, then all of these subcases are not satisfied. Thus, we particularly show the following claim.

Claim 4. Subcase 2-1-1 is not satisfied.

If f (x) = 1 and f (y) = 2, then the sum of the induced edge labels of F² is

\[\sum_{uv \in E(F_2)} (f(u) + f(v)) = \sum_{i=4}^{m+n+3} i = \frac{(m+n)(m+n+7)}{2}.\]

Since deg v = 1 for all v ∈ V (F2) − {x, y}, the sum of the vertex labels of F² is

\[\sum_{v \in V(F_2)} f(v) = \sum_{i=1}^{m+n+2} i = \frac{(m+n+2)(m+n+3)}{2}.\]

The equation m + n − 3 = (m − 1) f (x) + (n − 1) f (y) is also obtained from the fact that

\[\sum_{uv \in E(F_2)} (f(u) + f(v)) = \sum_{v \in V(F_2)} f(v) + (m-1) f(x) + (n-1) f(y).\]

However, it follows from our assumption that

\[(m-1) f(x) + (n-1) f(y) = m + 2n - 3.\]

This leads us to conclude that m + n − 3 = m + 2n − 3 so that n = 0, which is impossible. Thus, Claim 4 is true when f (x) = 1 and f (y) = 2. It remains to consider the case that f (x) = 2 and f (y) = 1. However, the argument for this case is entirely analogous to that of the preceding. This completes the proof of Claim 4.

Therefore, it follows from all the claims that µ^c (F2) ≥ 1 for every two positive integers m and n, proving the result.

The following corollary is an immediate consequence of Theorems 2.1 and 4.3.

Corollary 4.2. For every two positive integers m and n,

\[\alpha\left(S_m \cup S_n\right) = m + n + 2.\]

In light of the preceding result, it is now natural to explore the strong alpha-number of the forest S^m ∪ Sn, which is contained in the following theorem.

Theorem 4.4. For every two positive integers m and n, α^s (S^m ∪ Sn) = +∞.

Proof. Define the forest F ∼= S^m ∪ Sⁿ as in the proof of the preceding theorem. Now, assume, to the contrary, that α^s (F) = k for some positive integer k when m and n are positive integers. Then there exists an injective function f : V (F) → [0, k] such that

\[\left\{ \left|f\left(x\right)-f\left(y\right)\right|:xy\in E\left(F\right)\right\} =\left[1,m+n\right]\]

and there exists an integer λ so that min {f (x), f (y)} ≤ λ < max {f (x), f (y)} for every xy ∈ E (F). This means that one vertex in some pairs of adjacent vertices is labeled λ and the

other vertex in the pair is labeled λ + 1. Also, the integers 0, λ, λ + 1 are necessary in the elements of the set {f (v) : v ∈ V (F)}. From these observations, we distinguish two cases.

Case 1. Let F have partite sets U and V , where

\[U = \{x, y\} \text{ and } V = \{x_i : i \in [1, m]\} \cup \{y_i : i \in [1, n]\},\]

and, without loss of generality, assume that f (x) = 0 and f (y) = λ. It is true that if λ + 1 ∈ {f (xi) : i ∈ [1, m]}, then |f (x) − f (xi)| ≥ λ + 1 ≥ 2; so 1 ∈ {| / f (x) − f (y)| : xy ∈ E (F)}. Thus, λ + 1 ∈ {f (yi) : i ∈ [1, n]}, implying that 1 ∈ {|f (y) − f (yi)| : i ∈ [1, n]}. It is also true that if λ + 2 ∈ {f (xi) : i ∈ [1, m]}, then |f (x) − f (xi)| ≥ λ + 2 ≥ 3. It follows that 2 ∈ {| / f (x) − f (y)| : xy ∈ E (F)}. Thus, λ + 2 ∈ {f (yi) : i ∈ [1, n]}, implying that 2 ∈ {|f (y) − f (yi)| : i ∈ [1, n]}. Continuing in this manner, we see that l ∈ {|f (y) − f (yi)| : i ∈ [1, n]} for any l ∈ [1, n]. Consequently, we obtain

\[\{f(y_i): i \in [1, n]\} = [\lambda + 1, \lambda + n]\]

and

\[\{|f(y) - f(y_i)| : i \in [1, n]\} = [1, n],\]

which implies that f (xi) ≥ λ + n + 1 for any i ∈ [1, m]. This together with our assumption that f (x) = 0 implies that |f (x) − f (xi)| ≥ λ + n + 1 for any i ∈ [1, m]. However, λ ≥ 1; so |f (x) − f (xi)| ≥ n+ 2 for any i ∈ [1, m]. Hence, n+ 1 ∈ {| / f (x) − f (y)| : xy ∈ E (F)}, which is impossible.

Case 2. Let F have partite sets U and V , where

\[U = \{x\} \cup \{y_i : i \in [1, n]\} \text{ and } V = \{x_i : i \in [1, m]\} \cup \{y\}.\]

Then there are two subcases to pursue.

Subcase 2-1. Let f (x) = λ. Then f (yi) ≤ λ − 1 ( i ∈ [1, n] ). It is true that if f (y) = λ + 1, then |f (x) − f (xi)| ≥ 2 ( i ∈ [1, m] ) and |f (y) − f (yi)| ≥ 2 ( i ∈ [1, n] ). It follows that 1 ∈ {| / f (x) − f (y)| : xy ∈ E (F)}. Thus, λ + 1 ∈ {f (xi) : i ∈ [1, m]}, implying that 1 ∈ {|f (x) − f (xi)| : i ∈ [1, m]}. It is also true that if f (y) = λ + 2, then |f (x) − f (xi)| ≥ 3 ( i ∈ [1, m] ) and |f (y) − f (yi)| ≥ 3 ( i ∈ [1, n] ). It follows that 2 ∈ {| / f (x) − f (y)| : xy ∈ E (F)}. Thus, λ + 2 ∈ {f (xi) : i ∈ [1, m]}, implying that 2 ∈ {|f (x) − f (xi)| : i ∈ [1, m]}. Continuing in this manner, we see that l ∈ {|f (x) − f (xi)| : i ∈ [1, m]} ( l ∈ [1, m] ). Consequently, we obtain

\[\{f(x_i): i \in [1, m]\} = [\lambda + 1, \lambda + m]\]

and

\[\{|f(x) - f(x_i)| : i \in [1, m]\} = [1, m],\]

which implies that f (y) ≥ λ + m + 1. This together with the fact that f (yi) ≤ λ − 1 ( i ∈ [1, n] ) implies that |f (y) − f (yi)| ≥ m+2 ( i ∈ [1, n] ). Hence, m+1 ∈ {| / f (x) − f (y)| : xy ∈ E (F)}, which is impossible.

Subcase 2-2. Let f (x) = λ − l, where l ∈ [1, λ]. Then λ ∈ {f (yi) : i ∈ [1, n]}. It is true that if λ+1 ∈ {f (xi) : i ∈ [1, m]}, then |f (x) − f (xi)| ≥ l+1 ≥ 2 ( i ∈ [1, m] ) and |f (y) − f (yi)| ≥ 2 ( i ∈ [1, n] ). It follows that 1 ∈ {| / f (x) − f (y)| : xy ∈ E (F)}. Thus, f (y) = λ + 1.

Now, consider the function \(g:V(F)\to [1,\alpha_s(F)]\) such that \(g(v)=\alpha_s(F)-f(v)\) for all \(v\in V(F)\). Then \(g(u)\geq \alpha_s(F)-\lambda\) for all \(u\in U\) and \(g(v)\leq \alpha_s(F)-\lambda-1\) for all \(v\in V\). In particular, we have \(g(y)=\alpha_s(F)-\lambda-1\). It remains only to observe that an analogous argument to the preceding subcase can be applied to obtain a contradiction.

Before presenting our next result, we mention the consecutively super edge-magic property of paths obtained by Cattell [4]. For this purpose, let \(P_n\) denote the path with n vertices.

Theorem 4.5. For an end-vertex v of the path \(P_n\), there exists a consecutively super edge-magic labeling f of \(P_n\) such that f(v) = i for any \(i \in [1, n]\) if and only if n = 4s + 1 and \(f(v) \notin \{s + 1, 3s + 1\}\).

As the concept of induced subgraph will appear in the proof of our next result, we define this concept for the sake of clarity. If S is a nonempty subset of the vertex set V(G) of a graph G, then the subgraph \(\langle S \rangle\) of G induced by S is the graph having vertex set S and whose edge set consists of those edges of G incident with two elements of S. A subgraph S of S is called induced if S if S for some subset S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of S of

We are now prepared to present the following theorem.

Theorem 4.6. For all positive integers m and n,

\[\mu_c(P_m \cup S_n) = \begin{cases} 1 & \text{if } m = 2 \text{ or } 3, \\ 0 & \text{if } m \neq 2 \text{ or } 3. \end{cases}.\]

Proof. Let \(F \cong P_m \cup S_n\) be the forest with

\[V(F) = \{x_i : i \in [1, m]\} \cup \{y\} \cup \{y_i : i \in [1, n]\}\]

and

\[E(F) = \{x_i x_{i+1} : i \in [1, m-1]\} \cup \{y y_i : i \in [1, n]\}.\]

For m=1, label the vertices of degree 1 of F with the first n positive integers, the isolated vertex of F with n+1 and the remaining vertex with n+2. This gives a consecutively super edge-magic labeling of F when m=1. The result also follows from Theorem 4.3 when m=2 or 3. Thus, assume that m is an integer with \(m\geq 4\) and \(m\neq 6\), and define the induced subgraphs of F as follows. Let \(F_1\cong P_{m-1}\) and \(F_2\cong S_n\) be the induced subgraphs of F with

\[V\left(F_{1}\right)=\left\{ x_{i}:i\in\left[1,m\right]\right\} \text{ and }V\left(F_{2}\right)=\left\{ y\right\} \cup\left\{ y_{i}:i\in\left[1,n\right]\right\} .\]

For \(m \ge 4\) and \(m \ne 6\), it follows from Theorem 4.5 that there exists a consecutively super edgemagic labeling \(f_1\) of \(F_1\) with \(f_1(x_2) = 2\). On the other hand, there exists a consecutively super edge-magic labeling \(f_2\) of \(F_2\) such that \(f_2(y) = n + 1\) and \(f_2(y_i) = i\) for each \(i \in [1, n]\). With these knowledge in hand, consider the vertex labeling \(f: V(F) \to [1, m + n + 1]\) such that

\[f\left(v\right) = \begin{cases} \lfloor m/2 \rfloor + n + 1 & \text{if } v = x_1, \\ n + 2 + f_1\left(v\right) & \text{if } v = x_{2i-1} \text{ and } i \in [2, \lceil m/2 \rceil], \\ n + f_1\left(v\right) & \text{if } v = x_{2i} \text{ and } i \in [1, \lfloor m/2 \rfloor], \\ \lfloor m/2 \rfloor + 1 + f_2\left(v\right) & \text{if } v = y, \\ f_2\left(v\right) & \text{if } v = y_i \text{ and } i \in [1, n]. \end{cases}\]

Then f extends to a consecutively super edge-magic labeling of F with valence \(\lfloor m/2 \rfloor + 2m + 3n + 3\). In order to show this, notice first that if we let

\[U = \{x_{2i} : i \in [1, \lfloor m/2 \rfloor]\} \cup \{y_i : i \in [1, n]\}\]

and

\[V = \{x_{2i-1} : i \in [2, \lceil m/2 \rceil]\} \cup \{y\},\\]

then U and V form the partite sets of F, and

\[f(U) = [1, |m/2| + n]\] and \(f(V) = [|m/2| + n + 1, m + n + 1]\).

Next, to see that \(f\left(u\right)+f\left(v\right)+f\left(uv\right)=\lfloor m/2\rfloor+2m+3n+3\) for all \(uv\in E\left(F\right)\), where \(u\in U\) and \(v\in V\), notice that

\[\{f(u) + f(v) : uv \in E(F)\} = [|m/2| + n + 3, |m/2| + m + 2n + 1]\]

or, equivalently,

\[\{f(u) + f(v) : uv \in E(F)\} = [s, s + |E(F)| - 1],\]

where \(s = \lfloor m/2 \rfloor + n + 3\). It remains to notice that if m = 6, then the vertex labeling \(g : V(F) \to [1, n+7]\) such that \((g(x_i))_{i=1}^6 = (1, n+5, 4, n+7, 3, n+4)\), g(y) = 2, \(g(y_1) = n+6\) and \(g(y_i) = i+3\) (\(i \in [2, n]\)) induces a consecutively super edge-magic labeling of F with valence 2n+19.

Therefore, we conclude by means of Lemma 1.2 that F is consecutively super edge-magic for all positive integers m and n with \(m \ge 4\), which completes the proof.

Applying Theorems 2.1 and 4.6, we obtain the following result.

Corollary 4.3. For all positive integers m and n,

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Let \(F \cong P_m \cup S_n\), and consider the next cases. For the cases that m=2 or 3, it follows by Theorem 4.4 that \(\alpha_s(F)=+\infty\). For the cases that \(m\neq 2\) or 3, the consecutively super edgemagic labeling of F found in the proof of Theorem 4.6 satisfies the hypothesis of Corollary 2.1. This gives us the upper bound for \(\alpha_s(F)\), whereas the lower bound is obtained from Lemma 2.1 and Corollary 4.3 in this case. Therefore, we have the following result.

Corollary 4.4. For every two positive integers m and n,

\[\alpha_s(P_m \cup S_n) = \begin{cases} +\infty & \text{if } m = 2 \text{ or } 3, \\ m+n & \text{if } m \neq 2 \text{ or } 3. \end{cases}\]

5. Conclusions

We conclude this paper with some remarks on the conjectures stated in [10, 16] and three new conjectures.

The authors conjectured in [16] that if F is a forest of order p, then grac (F) is either p − 1 or p. It follows from Lemma 2.1 that all the results on alpha-numbers of forests obtained in the last section validate this conjecture. Moreover, as we mentioned in the beginning of the last section, µ^c (F) is finite for any forest F. Thus, we suspect the following conjecture to be true.

Conjecture 1. If F is a forest, then µ^c (F) ≤ 1.

From the work found in the literature, the authors suspect that Conjecture 1 may be very hard to solve. Hence, we also propose the following two conjectures that are weaker versions of Conjecture 1. To solve any of these two conjectures would be of great interest in the subject of graph labelings.

Conjecture 2. If F is a forest, then there exists a nonnegative integer k such that µ^c (F) ≤ k.

Analogous to the conjecture proposed by Figueroa-Centeno et al. [10] that µ^s (F) ≤ 1 for every forest F with two components, we now propose the following conjecture.

Conjecture 3. If F is a forest with two components, then µ^c (F) ≤ 1.

The authors conjectured in [16] that β (F) ≤ p and β^s (F) ≤ p for every forest F of order p. Of course, if Conjecture 1 is true, then it follows from Theorem 2.1 that α (F) ≤ p for every forest F of order p. Indeed, it follows from Lemma 2.1 that if Conjecture 1 is true, so are the aforementioned conjectures on beta-number and strong beta-number. Moreover, by Lemma 1.4, the truth of Conjecture 3 implies the truth of the aformentioned conjecture by Figueroa-Centeno et al. [10].

For the reader interested in different research directions in the same topic, the authors would like to recommend the paper by Ngurah and Simanjuntak [25].

References

• [1] B.D. Acharya and S.M. Hegde, Strongly indexable graphs, Discrete Math., 93 (1991) 123– 129.
• [2] M.Baca and M.Miller, ˇ Super edge-antimagic graphs: a wealth of problems and some solutions, Brown Walker Press, 2007, Boca Raton, FL, USA.
• [3] C. Barrientos, The gracefulness of unions of cycles and complete bipartite graphs, J. Combin. Math. Combin. Comput., 52 (2005) 69–78.
• [4] R. Cattell, Graceful labellings of paths, Discrete Math., 307 (2007) 3161–3176.
• [5] G. Chartrand and L. Lesniak, Graphs & Digraphs, Wadsworth & Brook/Cole Advanced Books and Software, Monterey, Calif. 1986.

• [6] H. Enomoto, A. Llado, T. Nakamigawa and G. Ringel, Super edge-magic graphs, ´ SUT J. Math., 34 (1998) 105–109.
• [7] R.M. Figueroa-Centeno and R. Ichishima, On the sequential number and super edge-magic deficiency of graphs, Ars Combin., 129 (2016) 157–163.
• [8] R.M. Figueroa-Centeno, R. Ichishima and F.A. Muntaner-Batle, On super edge-magic graphs, Ars Combin., 64 (2002) 81–95.
• [9] R.M. Figueroa-Centeno, R. Ichishima and F.A. Muntaner-Batle, On edge-magic labelings of certain disjoint unions of graphs, Australas. J. Combin., 32 (2005) 225–242.
• [10] R.M. Figueroa-Centeno, R. Ichishima and F.A. Muntaner-Batle, Some new results on the super edge-magic deficiency of graphs, J. Combin. Math. Combin. Comput., 55 (2005) 17– 31.
• [11] R.M. Figueroa-Centeno, R. Ichishima and F.A. Muntaner-Batle, On the super edge-magic deficiency of graphs, Ars Combin., 78 (2006) 33–45.
• [12] R.M. Figueroa-Centeno, R. Ichishima, F.A. Muntaner-Batle and M. Rius-Font, Labeling generating matrices, J. Combin. Math. Combin. Comput., 67 (2008) 189–216.
• [13] J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin., (2017) #DS6.
• [14] S.W. Golomb, How to number a graph, in Graph Theory and Computing, (ed. R.C. Read), Academic Press, New York (1972), 23–37.
• [15] S.M. Hegde and S.Shetty, Strongly k-indexable and super edge-magic labelings are equivalent, preprint.
• [16] R. Ichishima, S.C. Lopez, F.A. Muntaner-Batle and A. Oshima, On the beta-number of forests ´ with isomorphic components, Discuss. Math. Graph Theory, 38 (2018) 683–701.
• [17] R. Ichishima, F.A. Muntaner-Batle and A. Oshima, The measurements of closeness to graceful graphs, Australas. J. Combin., 62 (3) (2015) 197–210.
• [18] R. Ichishima and A. Oshima, On the super edge-magic deficiency and α-valuations of graphs, J. Indones. Math. Soc., Special Edition (2011) 59–69.
• [19] R. Ichishima and A. Oshima, On the super edge-magic deficiency of 2-regular graphs with two components, Ars Combin., 129 (2016) 437–447.
• [20] R. Ichishima and A. Oshima, Bounds for the gamma-number of graphs, Util. Math., 109 (2018) 313–325.
• [21] A. Kotzig and A. Rosa, Magic valuations of finite graphs, Canad. Math. Bull., 13 (1970) 451–461.

• [22] S.C. Lopez and F.A. Muntaner-Batle, ´ Graceful, Harmonious and Magic Type Labelings: Relations and Techniques, SpringerBriefs in Mathematics, Springer, Cham, 2017.
• [23] A.M. Marr and W.D. Wallis, Magic Graphs. Second ed. Birkhauser/Springer, New York, ¨ 2013.
• [24] F.A. Muntaner-Batle, Special super edge-magic labelings of bipartite graphs, J. Combin. Math. Combin. Comput., 39 (2001) 107–120.
• [25] A.A.G Ngurah and R. Simanjuntak, On the super edge-magic deficiency of join product and chain graphs, Electron. J. Graph Theory Appl., 7 (1) (2019), 157–167.
• [26] A. Oshima, Consecutively super edge-magic tree with diameter 4, Rev. Bull. Calcutta Math. Soc., 15 (2007) 87–90.
• [27] A. Oshima, R. Ichishima and F.A. Muntaner-Batle, New parameters for studying graceful properties of graphs, Electron. Notes Discrete Math., 60 (2017) 3–10.
• [28] G. Ringel and A. Llado, Another tree conjecture, ´ Bull. Inst. Combin. Appl., 18 (1996) 83–85.
• [29] A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Symposium, Rome, July 1966), Gordon and Breach, N. Y and Dunod Paris (1967), 349–355.
• [30] W.D. Wallis, Magic Graphs, Birkhauser, Boston, 2001. ¨