Electronic Journal of Graph Theory and Applications

Sigit Pancahayani^a, Rinovia Simanjuntak*,b,c, Saladin Uttunggadewa^b

^aDoctoral Program in Mathematics, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Jalan Ganesa 10 Bandung, Indonesia ^bCombinatorial Mathematics Research Group, Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung, Jalan Ganesa 10 Bandung, Indonesia ^cCentre for Research Collaboration in Graph Theory and Combinatorics, Indonesia

30122004@mahasiswa.itb.ac.id, rino@itb.ac.id, s-uttunggadewa@itb.ac.id *corresponding author

Let t and q be positive integers that satisfy \(\binom{t+1}{2} \leq q < \binom{t+2}{2}\) and let G be a simple and finite graph of size q. G is said to have ascending subgraph decomposition (ASD) if G can be decomposed into t subgraphs \(H_1, H_2, \ldots, H_t\) without isolated vertices such that \(H_i\) is isomorphic to a proper subgraph of \(H_{i+1}\) for \(1 \leq i \leq t-1\), where \(\{E(H_1), \ldots, E(H_t)\}\) is a partition of E(G). A graph that admits an ascending subgraph decomposition is called an ASD graph.

In this paper, we introduce a new type of magic labeling based on the notion of ASD. Let G be an ASD graph and \(f:V(G)\cup E(G)\to \{1,2,\ldots,|V(G)|+|E(G)|\}\) be a bijection. The weight of a subgraph \(H_i\) \((1\leq i\leq n)\) is \(w(H_i)=\sum_{v\in V(H_i)}f(v)+\sum_{e\in E(H_i)}f(e)\). If the weight of each ascending subgraph is constant, say \(w(H_i)=k, \ \forall \ 1\leq i\leq t\), then f is called an ASD-magic labeling of G and G is called an ASD-magic graph. We present general properties of ASD-magic graphs and characterize certain classes of them.

Keywords: decomposition, ascending subgraph decomposition, magic, labeling

Mathematics Subject Classification: 05C78

DOI: 10.5614/ejgta.2024.12.2.4

Received: 10 November 2023, Revised: 10 May 2024, Accepted: 10 June 2024.

1. Introduction

Let G and H be simple and finite graphs. If each edge of G belongs to at least one subgraph isomorphic to H, then G admits a H-covering. In 2005, Gutiérrez and Lladó introduced the H-magic labeling or the H-magic covering of a graph G. A bijection \(f:V(G)\cup E(G)\to \{1,2,...,|V(G)|+|E(G)|\}\) is called a H-magic labeling of G if there exists an integer E such that for any subgraph E of E which is isomorphic to E, the weight E is equal to E and E are E is equal to E. A graph E is said to be E-magic if it admits a E-magic labeling. Additionally, if E is equal to E, then E is called E-supermagic [5].

On the other hand, if each edge of G belongs to exactly one subgraph isomorphic to H, then G is said to admit a H-decomposition. Formally, let \(\mathcal{H} = \{H_i, i = 1, 2, 3, ..., t\}\) be a collection of t subgraphs of G. If \(H_i \cong H_j\), \(i \neq j\), \(E(H_i) \cap E(H_j) = \emptyset\), and \(\bigcup_{i=1}^t H_i = G\), then G is decomposable on H or G admits a H-decomposition [3]. Inayah et. al. in [6] then defined a H-magic decomposition of a graph G as a bijection \(f: V(G) \cup E(G) \to \{0, 1, 2, ..., |V(G)| + |E(G)|\}\) such that the weights of all subgraphs is constant. Recent results on H-magic covering and decomposition include \(P_h\)-covering of graphs [10] and \(K_h\)-decomposition of some block designs [7]. For more results, refer to Gallian's survey [4].

Note that the two previous magic labelings require that the weights be counted in subgraphs that are isomorphic to a certain graph. However, in 2023, Ashari \(et\,al.\) considered weights in subgraphs isomorphic to two nonisomorphic subgraphs when they introduced the (F,H)-simultaneously-magic labelings of graphs [2]. Here, we introduce a magic labeling in which all subgraphs are not isomorphic to each other. This labeling is based on a type of graph decomposition introduced in 1987 by Alavi \(et.\,al.\,[1].\)

Definition 1.1. [1] Let t and q be two positive integers satisfying \(\binom{t+1}{2} \leq q < \binom{t+2}{2}\). Let G be a simple and finite graph of size q. G admits an ascending subgraph decomposition if G can be decomposed into t subgraphs \(H_1, H_2, \ldots, H_t\) without isolated vertices such that \(H_i\) is isomorphic to a proper subgraph of \(H_{i+1}\) for \(1 \leq i \leq t-1\). In this case, G is called an ASD graph and \(H_1, H_2, \ldots, H_t\) is the ascending subgraphs of G.

It was conjectured that every graph of positive size has an ascending subgraph decomposition [1]. Until today, the conjecture remains open, although many families of graphs have been showed to be ASD. Refer to Liang and Fu survey [8] for some results on ASD graphs.

The definition of ascending subgraph decomposition motivates us to define a new type of magic labeling of a graph G admitting an ascending subgraph decomposition, where the weights are counted over the ascending subgraphs.

Definition 1.2. Let G be an ASD graph with \(\mathcal{H} = \{H_1, H_2, ..., H_t\}\) is a collection of t ascending subgraphs of G. Let f be a bijection which maps \(V(G) \cup E(G)\) onto \(\{1, 2, ..., |V(G)| + |E(G)|\}\). If there exists a constant k such that the weight of each subgraph is constant, that is \(w(H_i) = k\) for every \(1 \le i \le t\), then f is called an ASD-magic labeling of G.

If a graph G admits a collection of ascending subgraphs corresponding to an ASD-magic labeling of G, then G is ASD-magic.

In this paper, we characterize some classes of graphs admitting ASD-magic labeling, which include stars (Section 3), paths (Section 4), and cycles (Section 5). Some general properties of ASD-magic graphs are needed in characterizing the previously mentioned classes of graphs and are presented in Section 2.

2. General Properties of ASD-Magic Graphs

We start by observing the size of the smallest subgraph of an ASD graph.

Observation 2.1. If G is an ASD graph and \(H_i\), \(1 \le i \le t\) are ascending subgraphs of G, then the size of \(H_1\) is one or two.

Proof. It is clear that \[|E(H_i)| < |E(H_j)|\] for \(1 \le i < j \le t\). Assume that \(|E(H_1)| \ge 3\) and \(|E(H_{i+1})| = |E(H_i)| + 1\). Since we have \(t\) ascending subgraphs, then \(q = \sum_{i=1}^t |E(H_i)| \ge \sum_{i=1}^t (i+2) = \frac{t(t+5)}{2} \ge {t+2 \choose 2}\), a contradiction. It implies that \(|E(H_1)| < 3\).

In general, the decomposition of a graph in an ascending order is not unique. This is beneficial in the sense that in proving a graph is ASD-magic, there exist alternative decompositions to be labeled. On the other hand, this is also a drawback in verifying that a graph is not ASD-magic. To avoid checking all possible ASDs in proving that a graph is not ASD-magic, we define the following notions.

Let \(f: V(G) \cup E(G) \to 1, 2, ..., |V(G)| + |E(G)|\) be a bijection. The maximum weight of the smallest subgraph, \(w_{max}(H_1)\), is the weight when the vertex and edge sets of \(H_1\) are labeled with the largest labels, that is

\[w_{max}(H_1) = \sum_{i=1}^{|V(H_1)|+|E(H_1)|} (|V(G)|+|E(G)|-i+1).\] (1)

Let \(\mathfrak{H}\) be the collection of all ascending subgraph decompositions of G. The minimum number of vertices that belong to more than one subgraph over all possibilities of ascending subgraph decompositions is

\[c = \min_{\mathcal{H} \in \mathfrak{H}} \left\{ \sum_{i \neq j} |V(H_i) \cap V(H_j) \right\}\] (2)

Next, let \(C = \{c_i \mid i = 1, 2, ..., c\}\) be the set of intersection vertices with minimum cardinality. We define the smallest average weight of G by considering the label set of C as

\[\overline{w}_{min}(G) = \frac{1}{t} \left[ \sum_{i=1}^{|V(G)| + |E(G)|} i + \sum_{i=1}^{c} (d_i - 1) f(c_i) \right].\] (3)

where \(d_i\) is the number of subgraphs containing the intersection vertices \(c_i\).

The previously defined weight notions lead to the following necessary condition for an ASD-magic graph.

Lemma 2.1. Let G be an ASD graph and \(H_1\) be the smallest ascending subgraph of G. If G admits an ASD-magic labeling, then \(w_{max}(H_1) \geq \overline{w}_{min}(G)\).

Proof. For the contrary, suppose \(w_{max}(H_1) < \overline{w}_{min}(G)\). Then, there exists \(H_j\) where \(w(H_1) \neq w(H_j)\), a contradiction.

3. ASD-Magic Labelings for Stars

An ascending subgraph decomposition of stars was studied by Ma et. al. [9], where they proved that a star forest is an ASD graph.

Theorem 3.1. [9] Let G be a star forest of size \(\binom{t+1}{2}\) where each component has at least t edges. Then G admits an ascending subgraph decomposition where all subgraphs are stars.

Theorem 3.2. A star \(K_{1,n-1}\) is ASD-magic if and only if n = 2, 3, 4, 6, 10, 15.

Proof. Let \(\{H_i \mid i=1,2,...,t\}\) be a collection of t ascending subgraphs of \(K_{1,n-1}\). It is straightforward that any subgraph of a star is also a star. To prove that \(K_{1,n-1}\) admits an ASD-magic labeling, we have two cases to verify \(H_1 \cong P_2\) and \(H_1 \cong P_3\). Since the size of \(K_{1,n-1}\) satisfies \(\binom{t+1}{2} \leq n-1 < \binom{t+2}{2}\), then

\[t = \begin{cases} \lfloor \frac{-1 + \sqrt{8n - 7}}{2} \rfloor, & \text{for Case 1,} \\ \lceil \frac{-3 + \sqrt{1 + 8n}}{2} \rceil, & \text{for Case 2.} \end{cases}\] (4)

Case 1. \(H_1 \cong P_2\)

In this case, \(H_1\) needs three labels. Using the three largest label \(\{2n-1, 2n-2, 2n-3\}\), we have \(w_{max}(H_1) = 6n-6\). Moreover, since \(K_{1,n-1}\) has one center vertex which appears in each ascending subgraph, the smallest average weight of t subgraph is

\[\overline{w}_{min}(K_{1,n-1}) = \frac{1}{t} \left[ \sum_{i=1}^{2n-1} i + (t-1)(2n-3) \right] = \frac{2n^2 - 3n + 3}{t} + 2n - 3.\]

Applying Lemma 2.1 gives an inequality

\[6n - 6 \ge \frac{2n^2 - 3n + 3}{t} + 2n - 3 \tag{5}\]

which has solution when \(n \in [0.875, 1) \cup \{2\} \cup [4, 4.5]\). Since n must be an integer, then \(n \in \{2, 4\}\). So, in this case we conclude that if \(K_{1,n-1}\) admits an ASD-magic labeling, then n = 2, 4.

Case 2. \(H_1 \cong P_3\)

In this case, since \(H_1 \cong P_3\) has 2 edges, then \(n-1=\binom{t+2}{2}-1\), and it needs five labels. The five largest labels for \(H_1\) is \(\{2n-1,2n-2,2n-3,2n-4,2n-5\}\), such that \(w_{max}(H_1)=10n-15\) and

\[\overline{w}_{min}(K_{1,n-1}) = \frac{1}{t} \left[ \sum_{i=1}^{2n-1} i + (t-1)(2n-5) \right] = \frac{2n^2 - 3n + 5}{t} + 2n - 5.\]

Applying Lemma 2.1, we have an inequality

\[10n - 15 \ge \frac{2n^2 - 3n + 5}{t} + 2n - 5 \tag{6}\]

that has solution when \(n \in [2.5, \ 3] \cup (3, \ 20.13) \cup (21, \ 24.15) \cup (28, \ 28.16)\). This implies that a star \(K_{1,n-1}\) is ASD-magic only if n = 3, 6, 10, 15.

For the sufficiency, Figure 1 provides the ASD-magic labelings of a star \(K_{1,n-1}\) of order n=2,3,4,6,10,15.

Figure 1. ASD-magic labelings of the star \(K_{1,n-1}\)

4. ASD-Magic Labelings for Paths

Theorem 4.1. A path \(P_n\) admits an ASD-magic labeling if and only if n = 1, 2, 3, 4, 6, 7, 10, 15, 21, 28, and 36.

Proof. Let \(\{H_i \mid i=1,2...,t\}\) be a collection of t ascending subgraphs of \(P_n\). It is easy to see that \(P_n\) is ASD-magic for n=1,2,3, but for \(n\geq 4\) we have the following seven cases based on \(H_1\) and whether it contains an end vertex:

• 1. \(H_1 \cong P_2\) contains an end vertex;
• 2. \(H_1 \cong P_2\) does not contain an end vertex;
• 3. \(H_1 \cong P_3\) contains an end vertex;
• 4. \(H_1 \cong P_3\) does not contain an end vertex;
• 5. \(H_1 \cong 2P_2\) contains two end vertices;
• 6. \(H_1 \cong 2P_2\) does not contain an end vertex; and

7. \(H_1 \cong 2P_2\) contains exactly one end vertex.

From formula (1), we count the maximum weight of \(H_1\) for each case.

\[w_{max}(H_1) = \begin{cases} 6n - 6, & \text{for Cases 1 and 2,} \\ 10n - 15, & \text{for Cases 3 and 4,} \\ 12n - 21, & \text{for Cases 5, 6 and 7.} \end{cases}\] (7)

Since the size of \(P_n\) satisfies \(\binom{t+1}{2} \le n-1 < \binom{t+2}{2}\),

\[t = \begin{cases} \lfloor \frac{-1 + \sqrt{8n - 7}}{2} \rfloor, & \text{for Cases 1 and 2,} \\ \lceil \frac{-3 + \sqrt{1 + 8n}}{2} \rceil, & \text{for Cases 3, 4, 5, 6, and 7.} \end{cases}\] (8)

Case 1. \(H_1 \cong P_2\) contains an end vertex

Let \(q_1, q_2, ..., q_t\) be a sequence of size of \(H_i\) for \(1 \le i \le t\) and \(q_1 = 1\). To minimize the number of intersection vertices, \(H_i \cong P_{q_i+1} \ \forall i = 1, 2, ..., t\), and so c = t - 1. To find the smallest average weight, the label set of C must contain \(\{1, 2, ..., t - 2, 2n - 3\}\), where 2n - 3 is a label of a vertex of \(H_1\). Hence, the minimum average weight for \(P_n\) is

\[\overline{w}_{min}(P_n) \ge \frac{1}{t} \left[ \sum_{i=1}^{2n-1} i + \sum_{i=0}^{t-2} i + 2n - 3 \right] = \frac{2n^2 + n - 2}{t} + \frac{t - 3}{2}.\]

By Lemma 2.1,

\[6n - 6 \ge \frac{2n^2 + n - 2}{t} + \frac{t - 3}{2}\]

which gives the integer solution \(n \in \{4,7\}\). The ASD-magic labelings of \(P_4\) and \(P_7\) can be seen in Figure 2.

Figure 2. ASD-magic labelings of paths in Case 1

Case 2 \(H_1 \cong P_2\) does not contain an end vertex

Let \(q_1, q_2, ..., q_t\) be a sequence of the size of \(H_i\) for \(1 \le i \le t\) and \(q_1 = 1\). To minimize the number of intersection vertices, we divide the order set into two subcases: when \(4 \le n \le 6\) and \(n \ge 7\). For n = 4, the ascending subgraphs of \(P_4\) are \(H_1 \cong P_2\) and \(H_2 \cong 2P_2\). For n = 5, the ascending subgraphs of \(P_5\) are \(H_1 \cong P_2\) and \(H_2 \cong P_2 \cup P_3\). While for n = 6, the ascending subgraphs of \(P_6\) are \(H_1 \cong P_2\) and \(H_2 \cong 2P_3\) or \(H_1 \cong P_2\) and \(H_2 \cong P_2 \cup P_4\). Therefore, c = 2 when n = 4, 5, 6. Next, for each n = 4, 5, 6, and 6, we apply the largest labels for \(H_1\), the smallest labels for \(H_2\), and the two smallest labels of \(H_1\) are labels for the two intersection vertices. Then we derive

\[w_{max}(H_1) = \begin{cases} 18, & \text{if } n = 4, \\ 24, & \text{if } n = 5, \\ 30, & \text{if } n = 6. \end{cases}\] (9)

and

\[\overline{w}_{min}(P_n) = \begin{cases} 19.5, & \text{if } n = 4, \\ 30, & \text{if } n = 5, \\ 42.5, & \text{if } n = 6. \end{cases}\] (10)

From (9) and (10), we see that \(w_{max}(H_1) < \overline{w}_{min}(P_n)\) for n = 4, 5, 6, which means \(P_4\), \(P_5\), and \(P_6\) do not admit an ASD-magic labeling.

Subsequently, the ascending subgraphs for \(P_n, n \geq 7\) are \(H_i \cong P_{q_{i+1}}\), which implies c = t - 1. Since two of elements in C are two vertices in \(H_1\), then the label set for C must contain \(\{1, 2, ..., t - 3, 2n - 2, 2n - 3\}\) and the minimum average weight for \(P_n\) is

\[\overline{w}_{min}(P_n) \ge \frac{1}{t} \left[ \sum_{i=1}^{2n-1} i + \sum_{i=0}^{t-3} i + (2n-2) + (2n-3) \right] = \frac{2n^2 + 3n - 2}{t} + \frac{t-5}{2}.\]

By Lemma 2.1,

\[6n - 6 \ge \frac{2n^2 + 3n - 2}{t} + \frac{t - 5}{2},\]

with solution in \(n \in [0.875, 0.999)\), or no integer solution.

Case 3. \(H_1 \cong P_3\) contains an end vertex

Let \(q_1, q_2, ..., q_t\) be a sequence of the size of subgraph \(H_i\) for \(1 \le i \le t\) and \(q_1 = 2\). To minimize the number of intersection vertices, \(H_i \cong P_{q_i+1} \ \forall i = 1, 2, ..., t\), and so c = t - 1. Consider that one element of C is a vertex of \(H_1\), then the labels for C must contain \(\{1, 2, ..., t - 2, 2n - 5\}\) and the minimum average weight for \(P_n\) is

\[\overline{w}_{min}(P_n) \ge \frac{1}{t} \left[ \sum_{i=1}^{2n-1} i + \sum_{i=0}^{t-2} i + 2n - 5 \right] = \frac{2n^2 + n - 4}{t} + \frac{t - 3}{2}.\]

By Lemma 2.1,

\[10n - 15 \ge \frac{2n^2 + n - 4}{t} + \frac{t - 3}{2}\]

with solution in \(n \in [2,2.5] \cup (3,27.79] \cup (28,32.74] \cup (36,37.69]\). Using the fact that \(q = {t+2 \choose 2} - 1 = {t(t+3) \over 2}\) and \(n \ge 6\), if \(P_n\) admits an ASD-magic labeling, then n = 6,10,15,21. The ASD-magic labelings on paths in this case can be seen in Figure 3.

Case 4. \(H_1 \cong P_3\) does not contain an end vertex

Let \(q_1, q_2, ..., q_t\) be a sequence of size of \(H_i\) for \(1 \le i \le t\) and \(q_1 = 2\). To minimize the number of intersection vertices, we separate into two subcases: t = 2 and \(t \ge 3\). When t = 2 (n = 6), \(P_6\) admits an ASD-magic labeling as demonstrated in the Figure 4.

Subsequently, when \(t \ge 3\) the ascending subgraphs of \(P_n\) are \(H_i \cong P_{q_{i+1}}\), \(\forall i = 1, 2, ..., t\), and so c = t - 1. The label set for C must contain \(\{1, 2, ..., t - 3, 2n - 5, 2n - 4\}\) where two of its elements are the labels for two vertices in \(H_1\). Thus,

\[\overline{w}_{min}(P_n) = \frac{1}{t} \left[ \sum_{i=1}^{2n-1} i + \sum_{i=1}^{t-3} i + (2n-5) + (2n-4) \right] = \frac{2n^2 + 3n - 6}{t} + \frac{t-5}{2}.\]

Magic labeling on graph with ascending subgraph decomposition | S. Pancahayani et al.

\[P_{10}: \begin{array}{c} P_{10}: \\ 11 \ 10 \ 7 \ 4 \ 2 \ 1 \ 6 \ 5 \ 3 \ 9 \ 8 \\ k = 34 \end{array}\] \[P_{10}: \begin{array}{c} 19 \ 18 \ 17 \ 5 \ 11 \ 16 \ 6 \ 14 \ 10 \\ 4 \\ k = 70 \end{array}\] \[P_{15}: \begin{array}{c} 29 \ 28 \ 27 \ 12 \ 25 \ 24 \ 22 \ 21 \ 6 \\ 5 \ 3 \ 11 \ 13 \ 15 \ 17 \ 18 \ 20 \ 19^4 \end{array}\] \[P_{21}: \begin{array}{c} 41 \ 40 \ 39 \ 36 \ 37 \ 35 \ 32 \ 28 \ 27 \ 3 \ 31 \ 30 \ 26 \\ 14 \ 15 \ 16 \ 17 \ 19 \ 21 \ 29 \ 22 \ 23 \ 7 \ 9 \ 18 \ 24 \end{array}\] \[P_{21}: \begin{array}{c} 41 \ 40 \ 39 \ 36 \ 37 \ 35 \ 32 \ 28 \ 27 \ 3 \ 31 \ 30 \ 26 \\ 14 \ 15 \ 16 \ 17 \ 19 \ 21 \ 29 \ 22 \ 23 \ 7 \ 9 \ 18 \ 24 \end{array}\] \[P_{21}: \begin{array}{c} 41 \ 40 \ 39 \ 36 \ 37 \ 35 \ 32 \ 28 \ 27 \ 3 \ 31 \ 30 \ 26 \\ 14 \ 15 \ 16 \ 17 \ 19 \ 21 \ 29 \ 22 \ 23 \ 7 \ 9 \ 18 \ 24 \end{array}\]

Figure 3. ASD-magic labelings of paths in Case 3

And by Lemma 2.1,

\[10n - 15 \ge \frac{2n^2 + 3n - 6}{t} + \frac{t - 5}{2}\]

with solution \(n \in (3, 26.88] \cup (28, 31.84] \cup (36, 36.79]\). Using the fact that \(q = {t+2 \choose 2} - 1 = \frac{t(t+3)}{2}\) and \(n \ge 6\), if a path with \(t \ge 3\) admits an ASD-magic labeling, then its order is n = 6, 10, 15, and 21. The ASD-magic labelings of \(P_n\) in Case 4 are shown in Figure 4.

Figure 4. ASD-magic labelings of paths in Case 4

Case 5. \(H_1 \cong 2P_2\) contains two end vertices

The minimal number of intersection vertices can be derived utilizing the ascending subgraphs of \(P_{n-1}\) in Case 1. Here we add one more intersection vertex while preserving the number of ascending subgraphs. Thus, c=t that includes two vertices of \(H_1\). The label set for C contains \(\{1,2,...,t-2,2n-6,2n-5\}\), thus we obtain

\[\overline{w}_{min}(P_n) \ge \frac{1}{t} \left[ \sum_{i=1}^{2n-1} i + \sum_{i=1}^{t-2} i + (2n-6) + (2n-5) \right] = \frac{2n^2 + 3n - 10}{t} + \frac{t-3}{2}.\]

Due to (7), since \(H_1\cong 2P_2\), then \(w_{max}(H_1)=12n-21\). Using Lemma 2.1, solution of \(w_{max}(H_1)\geq \overline{w}_{min}(P_n)\) or \(12n-21\geq \frac{2n^2+3n-10}{t}+\frac{t-3}{2}\) is \(n\in[2,2.5]\cup(3,44.5]\cup(45,50.46]\cup(55,56.41]\). Using the fact that \(q=\binom{t+2}{2}-1=\frac{t(t+3)}{2}\) and \(n\geq 6\), if a path \(P_n\) admits an ASD-magic labeling, then its order is n=6,10,15,21,28, and 36. Conversely, the ASD-magic labelings of the paths in Case 5 are shown in Figure 5.

Figure 5. ASD-magic labelings of paths in Case 5

Case 6. \(H_1 \cong 2P_2\) does not contain an end vertex

Let \(q_1,q_2,...,q_t\) be a sequence of size of \(H_i\) for \(1 \le i \le t\) and \(q_1=2\). To minimize the number of intersection vertices, the ascending subgraphs of the paths for t=2,3, and 4 are as follows. For t=2 or n=6, the ascending subgraphs of \(P_6\) are \(H_1\cong 2P_2\) and \(H_1\cong 3P_2\). For t=3 or n=10, the ascending subgraphs of \(P_{10}\) are \(H_1\cong 2P_2\), \(H_2\cong P_4\), and \(H_3\cong P_2\cup P_4\). For \(t\ge 4\), the ascending subgraphs of \(P_n\) are \(H_1\cong 2P_2\), and for \(i\ge 2\), \(H_i\cong P_{q_i}\). Hence

\[c = \begin{cases} 4, & \text{if } t = 2, 3, 4 \\ t, & \text{if } t \ge 5. \end{cases}\]

For t=2,3 or 4 (n=6,10,15), to determine \(\overline{w}_{min}(P_n)\), the label set of all intersection vertices should contain the smallest labels of \(H_1\), that is \(\{2n-6,2n-5,2n-4,2n-3\}\). Consider that those labels are counted twice, so

\[\overline{w}_{min}(P_n) \ge \frac{1}{t} \left[ \sum_{i=1}^{2n} i + (2n-6) + (2n-5) + (2n-4) + (2n-3) \right] = \frac{2n^2 + 7n - 18}{t}.\]

Combining Formula (7) and Lemma 2.1, the solution of \(w_{max}(H_1) \ge \overline{w}_{min}(P_n)\) or \(12n-21 \ge \frac{2n^2+7n-18}{t}\) is \(n \in [1,1.5] \cup (3,42.74] \cup (45,48.74]\). Using the fact that \(q = {t+2 \choose 2} - 1 = \frac{t(t+3)}{2}\) and \(n \ge 6\), if a path \(P_n\) admits an ASD-magic labeling, then its order is n = 6,10, and 15.

Furthermore, for \(t \ge 5\), the label set for C contains \(\{1, 2, ..., t-5, 2n-6, 2n-5, 2n-4, 2n-3\}\) which includes the four smallest labels of \(H_1\). Therefore,

\[\overline{w}_{min}(P_n) \geq \frac{1}{t} \left[ \sum_{i=1}^{2n-1} i + \sum_{i=1}^{t-5} i + (2n-6) + (2n-5) + (2n-4) + (2n-3) \right]\] \[= \frac{2n^2 + 7n - 8}{t} + \frac{t-9}{2}.\]

Solution of the inequality \(w_{max}(H_1) \geq \overline{w}_{min}(P_n)\) or \(12n-21 \geq \frac{2n^2+7n-8}{t} + \frac{t-9}{2}\) is \(n \in (3,42.67] \cup (45,48.64]\). Using the fact that \(q = {t+2 \choose 2} - 1 = \frac{t(t+3)}{2}\) and \(n \geq 6\), if \(t \geq 5\), if \(P_n\) admits an ASD-magic labeling, then its order is n = 6,10,15,21,28,36. On the other hand, the ASD-magic labelings on paths in Case 6 can be seen in Figure 6.

Figure 6. ASD-magic labelings of paths in Case 6

Case 7. \(H_1 \cong 2P_2\) contains exactly one end vertex

The minimal number of intersection vertices can be derived utilizing the ascending subgraphs for \(P_{n-1}\) in Case 2. Here we add one more intersection vertex while preserving the number of ascending subgraphs. Thus, c=t that includes three vertices of \(H_1\). Now, consider two subcases for t=2 and \(t\geq 3\). When t=2 or t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6, t=6

Figure 7. For \(t \ge 3\) or \(n \ge 10\), the label set for all the intersection vertices contains \(\{1, 2, ..., t - 3, 2n - 6, 2n - 5, 2n - 4, 2n - 3\}\) and we obtain

\[\overline{w}_{min}(P_n) \geq \frac{1}{t} \left[ \sum_{i=1}^{2n-1} i + \sum_{i=1}^{t-3} i + (2n-6) + (2n-5) + (2n-4) \right] = \frac{2n^2 + 5n - 12}{t} + \frac{t-5}{2}.\]

By Lemma 2.1, the solution of the inequality \(w_{max}(H_1) \geq \overline{w}_{min}(P_n)\) or \(12n-21 \geq \frac{2n^2+5n-12}{t} + \frac{t-5}{2}\) is \(n \in (3,43.57] \cup (45,49.53] \cup (55,55.49]\). Using the fact that \(q = \binom{t+2}{2} - 1 = \frac{t(t+3)}{2}\) and \(n \geq 6\), if a path in case 7 admits an ASD-magic labeling, then n = 6,10,15,21,28, and 36. To complete the proof, we present Figure 7 to illustrate the ASD-magic labelings of all paths in Case 7.

Figure 7. ASD-magic labelings of paths in Case 7

5. ASD-Magic Labelings for Cycles

In this last section, we characterize ASD-magic cycles.

Theorem 5.1. Cycle \(C_n\) is ASD-magic if and only if n = 3, 5, 9, 14, 20, 27, and 35.

Proof. The three cases to be considered are

• 1. \(H_1 \cong P_2\);
• 2. \(H_1 \cong P_3\); and

3. \[H_1 \cong 2P_2\].

As a consequence, we have

\[w_{min}(H_1) = \begin{cases} 6n - 3, & \text{for Case 1,} \\ 10n - 10, & \text{for Case 2,} \\ 12n - 15, & \text{for Case 3.} \end{cases}\]

Since the size of \(C_n\) satisfy \(\binom{t+1}{2} \leq n < \binom{t+2}{2}\), we obtain

\[t = \begin{cases} \lfloor \frac{-1 + \sqrt{1 + 8n}}{2} \rfloor, & \text{for Case 1,} \\ \lceil \frac{-3 + \sqrt{9 + 8n}}{2} \rceil, & \text{for Cases 2 and 3.} \end{cases}\]

Next, we shall count \(\overline{w}_{min}(C_n)\) for each case so that we can apply Lemma 2.1.

Case 1. \[H_1 \cong P_2\]

The minimal number of intersection vertices can be derived utilizing the ascending subgraphs as in Case 1 of the proof of Theorem 4.1 by joining the two ends of the path. Thus, we obtain c=t. To obtain the smallest average weight of a cycle, the set of labels for the intersection vertices must contain \(\{1, 2, ..., t-2, 2n-2, 2n-1\}\). This set involves two labels of \(H_1\), so we have

\[\overline{w}_{min}(C_n) \ge \frac{1}{t} \left[ \sum_{i=1}^{2n} i + \sum_{i=1}^{t-2} i + (2n-2) + (2n-1) \right] = \frac{2n^2 + 5n - 2}{t} + \frac{t-3}{2}.\]

By Lemma 2.1, the integer solution for \(w_{max}(H_1) \geq \overline{w}_{min}(C_n)\) or \(6n-3 \geq \frac{2n^2+5n-2}{t} + \frac{t-3}{2}\) is n=3. Therefore, the only cycle admitting an ASD-magic labeling in case 1 is \(C_3\). Moreover, the ASD-magic labeling of \(C_3\) is given in Figure 8.

Figure 8. ASD-magic labeling of \(C_3\)

Case 2. \(H_1 \cong P_3\)

The minimal number of intersection vertices can be derived utilizing the ascending subgraphs as in Case 3 of the proof of Theorem 4.1 by joining the two ends of the path. Thus, we get c=t. Subsequently, to obtain the smallest average weight of a cycle, the set of labels for the intersection vertices must contain \(\{1, 2, ..., t-2, 2n-4, 2n-3\}\), which include two labels of \(H_1\): 2n-4 and 2n-3. Hence,

\[\overline{w}_{min}(C_n) \ge \frac{1}{t} \left[ \sum_{i=1}^{2n} i + \sum_{i=1}^{t-2} i + (2n-4) + (2n-3) \right] = \frac{2n^2 + 5n - 6}{t} + \frac{t-3}{2}.\]

By Lemma 2.1 the solution for \(w_{max}(H_1) \geq \overline{w}_{min}(C_n)\) or \(10n-10 \geq \frac{2n^2+5n-2}{t} + \frac{t-3}{2}\) is \(n \in (1,1.5) \cup (2,26.3) \cup (27,31.25) \cup (35,36.2)\). Using the fact that \(q = {t+2 \choose 2} - 1 = \frac{t(t+3)}{2}\) and \(n \geq 5\), if a cycle admits an ASD-magic labeling, then the order is n = 5,9,14,20. Moreover, the ASD-magic labelings of \(C_n\) in Case 2 are given in Figure 9.

Figure 9. ASD-magic labelings of cycles in Case 2

Case 3. \(H_1 \cong 2P_2\)

The minimal number of intersection vertices can be derived utilizing the ascending subgraphs as in Cases 6 or 7 of the proof of Theorem 4.1. Thus, for t=2 we have c=2 and for \(t\geq 3\) we have c=t+1. For t=2 or n=5, \(C_5\) admits an ASD-magic labeling as shown in the Figure 10. For \(t\geq 3\), to find the smallest average weight of cycle, the set of labels for the intersection vertices must contain \(\{1,2,...,t-3,2n-5,2n-4,2n-3,2n-2\}\), where 2n-5,2n-4,2n-3, and 2n-2 are labels for four vertices in \(H_1\). Hence,

\[\overline{w}_{min}(C_n) \geq \frac{1}{t} \left[ \sum_{i=1}^{2n} i + \sum_{i=1}^{t-3} i + (2n-5) + (2n-4) + (2n-3) + (2n-2) \right]\] \[= \frac{2n^2 + 9n - 11}{t} + \frac{t-5}{2}.\]

By Lemma 2.1, the solution of inequality \(w_{max}(H_1) \geq \overline{w}_{min}(C_n)\) or \(12n-15 \geq \frac{2n^2+9n-13}{t} + \frac{t-3}{2}\) is \(n \in [0.5,1] \cup (2,41.98] \cup (44,47.95]\). Using the fact that \(q = {t+2 \choose 2} - 1 = \frac{t(t+3)}{2}\) and \(n \geq 5\), if a cycle \(C_n\) admits an ASD-magic labeling then its order is n=5,9,14,20,27, and 35. To complete the proof, Figure 10 presents the ASD-magic labelings of cycles in case 3.

6. Remark and Open Problems

In this paper, we introduce the notion of ASD-magic labeling, a natural magic labeling arising from the ascending subgraph decomposition. From our preliminary results on characterizing ASD-magic stars, paths, and cycles, few graphs seem to be ASD-magic. However, we can still ask several general questions regarding ASD-magic labeling.

Figure 10. ASD-magic labelings of cycles in Case 3

Problem 1. If G is an ASD-magic graph of order n, what are the upper and lower bounds of the magic constant k, as functions of n?

Problem 2. Does there exist an infinite graph class where most of the graphs in that class are ASD-magic?

Problem 3. If G and H are two ASD-magic graphs, which binary graph operation ◦ preserves the ASD-magicness of G ◦ H?

Problem 4. If we relax the bijection condition in the ASD-magic labeling to injection, is it possible to have ASD-magic injection for all graphs?

Acknowledgement

This research was supported by Penelitian Disertasi Doktor 2023 (Number 307/IT1.B07.1/SPP-LPPM/VI/2023) funded by the Directorate General of Higher Education, Research, and Technology, Ministry of Education, Culture, Research, and Technology, Republic of Indonesia. The first author has been supported by LPDP Scholarship from the Ministry of Finance, Republic of Indonesia.

References

• [1] Y. Alavi, A.J. Boals, G. Chartrand, P. Erdos, and O.R. Oellermann, The Ascending Subgraph ˝ Decomposition Problem, Congressus Numeratium 58 (1987), 7–14.
• [2] Y.F. Ashari, A.N.M. Salman, R. Simanjuntak, A. Semanicov ˇ a-Fe ´ nov ˇ cˇ´ıkova, and M. Baca, ´ On (F, H)-simultaneously-magic labelings of graphs, Electron. J. Graph Theory Appl. 11(1) (2023) 49–64.
• [3] P. Erdos, A.W. Goodman, and L. P ˝ osa, The representation of a graph by set intersections, ´ Canad. J. Math, 18 (1966), 106–112.
• [4] J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin., 24 (2022) # DS6.
• [5] A. Gutierrez and A. Llad ´ o, Magic coverings, ´ J. Combin. Math. Combin. Comput. 55 (2005), 43–56.
• [6] N. Inayah, A. Llado and J. Moragas, Magic and antimagic ´ H-decomposition, Discrete Math. 312 (2012), 1367–1371.
• [7] Z. Liang, On magic total labelings in combinatorial designs, J. Information Optimization Sci., 45 (2024), 47–56.
• [8] Z. Liang and H. Fu, On Ascending Subgraph Decomposition of Graphs, J. Discrete Math. Sci. Cryptography 20 (2017),1135–1149.
• [9] K. Ma, H. Zhuo, and J. Zhuo, On The Ascending Star Subgraph Decomposition of Star Forest, Combinatorica 14 (1994), 307–320.
• [10] T.K. Maryati, F.F. Hadiputra, and A.N.M. Salman, Forbidden family of Ph-magic graphs, Electron. J. Graph Theory Appl. 12(1) (2024), 43–54.