The Integer-Magic Spectra of Trees

Carbonero, Alvaro; Obata, Dylan

doi:10.61091/jcmcc119-26

Abstract

References

Journal of Combinatorial Mathematics and Combinatorial Computing

Volume 119
Pages: 265-276

Research article

The Integer-Magic Spectra of Trees

^¹, ^¹

¹University of Nevada, Las Vegas, USA

Received: 11/06/2021
Accepted: 22/02/2021
Published: 31/03/2024

Copyright Link
License

Abstract

For any positive integer $h$ , a graph $G = (V, E)$ is said to be $h$ -magic if there exists a labeling $l : E (G) \to Z_{h} - {0}$ such that the induced vertex set labeling $l^{+} : V (G) \to Z_{h}$ defined by
$l^{+} (v) = \sum_{u v \in E (G)} l (u v)$
is a constant map. The integer-magic spectrum of a graph $G$ , denoted by $I M (G)$ , is the set of all $h \in N$ for which $G$ is $h$ -magic. So far, only the integer-magic spectra of trees of diameter at most five have been determined. In this paper, we determine the integer-magic spectra of trees of diameter six and higher.

Keywords: Integer-magic spectrum, Tree diameter, Magic labeling

1. Introduction

In this paper all graphs are connected, finite, simple, and undirected. For graph theory notations and terminology not described in this paper, we refer the readers to [1]. Let $G = (V, E)$ be a graph. For an abelian group $A,$ written additively, any mapping $l : E (G) \to A - {0}$ is called a labeling. Given an edge labeling $l$ , we can define a labeling of the vertices $l^{+} : V (G) \to A$ such that $l^{+} (v) = \sum_{u v \in E (G)} l (u v);$ that is, $l^{+} (v)$ is the sum of the labels of all the edges incident with $v$ . If there is a labeling $l$ such that $l^{+}$ is constant, then we say $G$ is an $A$ -magic graph and we call $l$ an $A$ -magic labeling. If $G$ is not $A$ -magic for every abelian group $A$ , then we say $G$ is non-magic. On the other hand, if $G$ is $A$ -magic for every abelian group $A$ , we say that $G$ is fully magic.

For convenience and to follow convention, we will use the notation $h$ -magic, where $h > 1$ , to indicate $Z_{h}$ -magic. Similarly, if $l$ is a $Z_{h}$ -magic labeling, we say $l$ is an $h$ -magic labeling. It is pertinent to mention that there is another definition of an $h$ -magic graph [2]; this one is a different generalization of magic graphs and so it does not relate to the topics covered in this paper.

Definition 1. For a graph G, let the integer-magic spectrum of $G$ , denoted by $I M (G)$ , be the set of all integers $h$ for which $G$ is $h$ -magic.

The integer-magic spectra of trees of diameter at most five have already been determined [3, 4]. In this paper, we generalize these previous results and characterize the integer-magic spectra of trees of arbitrary diameter. For a compilation of results regarding the integer-magic spectra of other families of graphs, we refer the reader to [5].

The term pendant vertex will refer to vertices with degree one. Similarly, the term pendant edge will refer to edges which are incident to pendant vertices. Note that a pendant vertex will have the same label as the pendant edge incident to it, so in order for $l^{+}$ to be constant, all pendent edges must have the same label. We will reserve the variable $x$ for the label that every pendant edge must have. Consequently, for $l$ to be an $h$ -magic labeling, we need $l^{+} (v) \equiv x \mod h$ for every vertex $v$ .

Figure 1: A Typical Tree of Diameter $6$

2. Notation for Trees

To determine the integer-magic spectrum of any tree, we need to develop notation that applies to trees of any diameter. To achieve this, we use the fact that trees of even diameter have as a center a single vertex, and that trees of odd diameter have as a center the path $P_{2}$ . From now on, $c$ will denote the vertex at the center of a tree of even diameter; similarly, $c_{1}$ and $c_{2}$ will denote the vertices at the center of a tree of odd diameter. Also, to simplify the statement of our theorems, we will use $T_{n}$ to refer to a tree of diameter $n$ .

We start by describing vertices in terms of their distance from the center.

Definition 2. For a tree $T_{2 k}$ and an integer $i \geq 0$ , let $D_{i} := {v \in V (T_{2 k}) : d (v, c) = i} .$

Trees of diameter $2 k + 1$ have the added complication of having two vertices at the center. For the sake of having formal definitions, we need to distinguish those vertices that are closer to $c_{1}$ from those that are closer to $c_{2}$ . With this objective, we define the function $δ : V (T_{2 k + 1}) \to N \cup {0}$ where $δ (v) = min {d (v, c_{1}), d (v, c_{2})}$ .

Definition 3. For a tree $T_{2 k + 1}$ and an integer $i \geq 0$ , let $D_{i} := {v \in V (T_{2 k + 1}) : δ (v) = i} .$

We are abusing notation by using $D_{i}$ for both even and odd diameter trees. However, for our purposes, their definitions are equivalent. In both cases, $D_{i}$ is the collection of vertices at distance $i$ from the center. See Figure 2 for an example.

Figure 2: A Tree $T_{6}$ with the Members of $D_{2}$ Highlighted in Red

Note that for both $2 k$ and $2 k + 1$ diameters, $D_{d} = \emptyset$ if $d > k$ ; otherwise, the diameter would be bigger. Furthermore, if the tree has diameter $2 k$ , then by definition there must be at least two pendant vertices that are distance $k$ away from $c$ ; similarly, for $T_{2 k + 1}$ , $c_{1}$ and $c_{2}$ each must have at least one pendant vertex that is $k$ away. Thus, for both odd and even diameters, if $1 \leq i \leq k$ , then $| D_{i} | \geq 2$ . Additionally, even diameters have $D_{0} = {c}$ , and odd diameters have $D_{0} = {c_{1}, c_{2}} .$ Finally, we note that, for any $n$ , if $u v \in E (T_{n})$ and $u \in D_{m}$ , then either $v \in D_{m + 1}$ or $v \in D_{m - 1}$ because $u$ and $v$ are adjacent, so the difference in their distance from the center is exactly one.

To discuss $h$ -magic labelings for trees, we need a way to talk about the subgraph that “branches out” of a vertex. With this objective in mind, we define the branches of $T_{n}$ . To simplify the statement of these definitions, we will use the term $P (u, v)$ , where $u, v \in V (T_{n})$ , to refer to the vertex set of the unique path in $T_{n}$ from $u$ to $v$ .

Definition 4. For a tree $T_{2 k}$ and $u \in V (T_{2 k}) ∖ {c}$ , let the branch of $u$ , or $B^{u}$ , be the induced subgraph of $T_{2 k}$ with vertex set: ${v \in V (T_{2 k}) : d (c, u) \leq d (c, v) and \forall w \in P (u, v) d (c, u) \leq d (c, w)} .$ Furthermore, define $B^{c} = T_{2 k}$ .

Informally, $B^{u}$ is the subgraph of $T_{2 k}$ that extends from $u$ and outwards to the pendant vertices. We now make an equivalent definition for trees of odd diameter.

Definition 5. For a tree of $T_{2 k + 1}$ and $u \in V (T_{2 k + 1}) ∖ {c_{1}, c_{2}}$ , let the branch of $u$ , or $B^{u}$ , be the induced subgraph of $T_{2 k + 1}$ with vertex set: ${v \in V (T_{2 k + 1}) : δ (u) \leq δ (v) and \forall w \in P (u, v) δ (u) \leq δ (w)} .$ Furthermore, let $B^{c_{1}}$ be the induced subgraph with vertex set: ${v \in V (T_{2 k + 1}) : δ (c_{1}) \leq δ (v) and c_{2} \notin P (v, c_{1})} .$ The definition of $B^{c_{2}}$ follows similarly.

Figure 3: A Tree $T_{7}$ with $B^{v}$ Highlighted in Red

If $v \in V (B^{u})$ and $v \neq u$ , then we say $v$ extends from $u$ . An important observation to make about these branches is that if $u v \in E (T_{n})$ , with $u \in D_{m}$ and $v \in D_{m + 1}$ , then $B^{v}$ is a subgraph of $B^{u}$ since all the vertices that extend from $v$ also extend from $u$ . In general, the branch of any vertex that extends from $u$ is a subgraph of $B^{u}$ . We now create a term that combines the objectives behind $D_{m}$ and $B^{u}$ .

Definition 6. For a tree $T_{n}$ , a vertex $u \in V (T_{n})$ and an integer $m \geq 0$ , let $D_{m}^{u} := D_{m} \cap V (B^{u}) .$

Informally, $D_{m}^{u}$ is the collection of vertices at distance $i$ from the center that also extend from $u$ . An important observation is that if $u \in D_{m}$ and $u$ is not a pendant vertex, then all the vertices in $D_{m + 1}^{u}$ are adjacent to $u$ because they extend from $u$ and are distance one away. On the other hand, if $u$ is a pendant vertex, then it must be that $D_{m + 1}^{u} = \emptyset$ because nothing would be able to extend from $u$ . Finally, if $u \in D_{m}$ , then $D_{m}^{u} = {u}$ because all other vertices in $V (B^{u})$ must be further away from the center than $u$ .

Having the same notation for both even and odd diameter trees allows us to make reference to trees in general without having to specify the parity of its diameter; when the parity of the diameter of the tree is important, we will separate the cases. We now prove a result that makes no reference to $h$ -magic labelings; it is a general fact about trees. A special case of the result will be extensively used in the next section.

Theorem 1. Let $T_{n}$ be a tree, let $p$ and $m$ be integers where $p > m$ , and let $u$ be a vertex in $D_{m}$ such that the set $D_{p}^{u}$ is nonempty. If $D_{p}^{u} = {w_{1}, w_{2}, \dots, w_{α}}$ , then, for every integer $d$ such that $d > p$ , $\begin{matrix} (1) & \sum_{i = 1}^{α} | D_{d}^{w_{i}} | = | D_{d}^{u} | . \end{matrix}$

Proof. Set $k = f l o o r \frac{n}{2}$ . If $d > k$ , the result is trivial since all the sets in (1) are empty. Thus, assume that $d \leq k$ .

Observe that the sets $D_{d}^{w_{1}}, D_{d}^{w_{2}}, \dots,$ and $D_{d}^{w_{α}}$ are all pairwise disjoint since their corresponding branches in $T_{n}$ do not overlap. Thus, $| ⋃_{1 \leq i \leq α} D_{d}^{w_{i}} | = \sum_{i = 1}^{α} | D_{d}^{w_{i}} | .$ We finish the proof by showing that $⋃_{1 \leq i \leq α} D_{d}^{w_{i}} = D_{d}^{u}$ . Let $v \in D_{d}^{w_{i}}$ for some $i$ where $1 \leq i \leq α$ . By definition, $v \in D_{d}$ and $v \in V (B^{w_{i}})$ . Since $w_{i}$ extends from $u$ , $B^{w_{i}}$ is a subgraph of $B^{u}$ . Thus, $v \in V (B^{u})$ . It follows that $v \in D_{d}^{u}$ . Now let $v \in D_{d}^{u}$ . Then $v \in V (B^{u})$ . Since $v$ is further away from the center than any of the vertices in $D_{p}^{u}$ , the path from $u$ to $v$ must go through $w_{i}$ for some $i$ . That is, $v$ extends from $w_{i}$ , and so $v \in V (B^{w_{i}})$ . Since $v \in D_{d}$ , $v \in D_{d}^{w_{i}}$ .

In the next section, we will use the special case of $p = m + 1$ since, as discussed before, $D_{m + 1}^{u}$ consists of vertices adjacent to $u$ . For convenience and future reference, we state it explicitly.

Corollary 1. For a tree $T_{n}$ , let $u$ be a vertex in $D_{m}$ such that $u$ is not a pendant vertex. If $D_{m + 1}^{u} = {w_{1}, w_{2}, \dots, w_{α}}$ , then, for every $d$ such that $d > m + 1$ , $\sum_{i = 1}^{α} | D_{d}^{w_{i}} | = | D_{d}^{u} | .$

3. The Forced Labeling $f$

In an $h$ -magic labeling, every pendant edge is forced to have the same label. We will show that in trees this notion of a “forced” labeling extends beyond pendant edges.

We start by showing a method for labeling edges that makes $l^{+}$ constant with the exception of the vertices at the center. The method will depend on the labeling assigned to the pendant edges, though it will not guarantee that the edge labeling does not include 0 in its range.

In Figure 4, we see such method applied. We can label the edges closer to the center according to the label of the edges further away in such a way that their common vertex gets the constant label. For instance, for $v$ , the sum of the labels of the edges further away is $- 3 x$ . Thus, the label of the edge closer to the center needs to be $4 x$ so that $l^{+} (v) = - 3 x + 4 x = x$ . By using the notation we developed in the previous section, we can define a function that calculates the number that multiplies the $x$ for each edge.

Figure 4: Edges Labelled Such That $L^{+}$ Is Constant

Definition 7. For a tree $T_{2 k}$ , define $f : E (T_{2 k}) \to Z$ such that if $u v \in E (T_{2 k})$ , $u \in D_{m}$ and $v \in D_{m - 1}$ , then $f (u v) := (- 1)^{k - m + 1} \sum_{i = 1}^{k - m + 1} (- 1)^{i} | D_{k - i + 1}^{u} | .$ Furthermore, for a tree $T_{2 k + 1}$ , define $f : E (T_{2 k + 1}) \to Z$ such that if $u v \in E (T_{2 k + 1}) ∖ {c_{1} c_{2}}$ , $u \in D_{m}$ and $v \in D_{m - 1}$ , then $f (u v) := (- 1)^{k - m + 1} \sum_{i = 1}^{k - m + 1} (- 1)^{i} | D_{k - i + 1}^{u} | .$ As for $c_{1} c_{2}$ , let $f (c_{1} c_{2}) := (- 1)^{k + 1} \sum_{i = 1}^{k + 1} (- 1)^{i} | D_{k - i + 1}^{c_{1}} | .$

The definition of $f$ for odd diameter trees is more complicated because there is an extra edge at the center to consider. For edges other than that one, $f$ is the same for even and odd diameters.

Note that, for even diameters, $f$ cannot guarantee that $l^{+} (c) = x$ . A similar problem happens for odd diameters. Although there is an edge at the center, this edge can only guarantee the constant label for $c_{1}$ or $c_{2}$ , but not always both. We arbitrarily chose to secure the constant label for $c_{1}$ . Another problem with this method is the possibility that $f (e) = 0$ for some edge $e$ . If that happens, then this method cannot be applied to construct an $h$ -magic labeling since $0$ cannot be assigned to an edge. These problems, however, do not happen in $h$ -magic graphs. The proof of this fact follows

Lemma 1. Let $T_{n}$ be an $h$ -magic tree where $l$ is an $h$ -magic labeling. If the pendant edges have label $x$ , then for every edge $e$ , $l (e) \equiv x f (e) \mod h .$

Proof. We first prove the statement for $n = 2 k$ . Define ${\hat{D}}_{m} = {u v \in E (T_{2 k}) : u \in D_{m} and v \in D_{m - 1}}$ for $m$ such that $1 \leq m \leq k$ . This partitions $E (T_{2 k})$ into $k$ sets. We will prove the statement by using the principle of backwards induction on $m$ .

For the base case, let $u v \in {\hat{D}}_{k}$ where $u \in D_{k}$ and $v \in D_{k - 1}$ . Since $u \in D_{k}$ , then $u v$ is a pendant edge. By definition, $l (u v) = x$ , and so $\begin{aligned} x f (u v) & = x (- 1)^{k - k + 1} \sum_{i = 1}^{k - k + 1} (- 1)^{i} | D_{k - i + 1}^{u} | \\ = x | D_{k}^{u} | \\ = x \\ = l (u v) \mod h . \end{aligned}$ We used the fact that for all $u \in D_{i}$ , $| D_{i}^{u} | = 1$ .

Now assume that the statement is true for all edges in ${\hat{D}}_{m}$ . Let $u v \in {\hat{D}}_{m - 1}$ , where $u \in D_{m - 1}$ , so $v \in D_{m - 2}$ . Assume $u$ is a pendant vertex. By definition, $l (u v) = x$ , and so $\begin{aligned} x f (u v) & = x (- 1)^{k - m + 1 + 1} \sum_{i = 1}^{k - m + 1 + 1} (- 1)^{i} | D_{k - i + 1}^{u} | \\ = x (- 1)^{k - m} (- | D_{k}^{u} | + \dots + (- 1)^{k - m + 2} | D_{m - 1}^{u} |) \\ = x (- 1)^{k - m} (0 + (- 1)^{k - m}) \\ = x \\ = l (u v) \mod h . \end{aligned}$ We used the fact that, since $u$ is a pendant vertex, $| D_{i}^{u} | = 0$ for all $i > m - 1$ .

Assume then that $u$ is not a pendant vertex. Let $D_{m}^{u} = {w_{1}, w_{2}, \dots, w_{α}}$ . Since $l$ is an $h$ -magic labeling, $l^{+} (u) = l (u v) + \sum_{i = 1}^{α} l (u w_{i}) \equiv x \mod h .$ But $u w_{i} \in {\hat{D}}_{m}$ for each $1 \leq i \leq α$ , so we can apply the induction hypothesis and obtain $\begin{aligned} \sum_{i = 1}^{α} l (u w_{i}) & \equiv \sum_{i = 1}^{α} x f (u w_{i}) \\ = \sum_{i = 1}^{α} x (- 1)^{k - m + 1} \sum_{j = 1}^{k - m + 1} (- 1)^{j} | D_{k - j + 1}^{w_{i}} | \\ = x (- 1)^{k - m + 1} \sum_{i = 1}^{α} \sum_{j = 1}^{k - m + 1} (- 1)^{j} | D_{k - j + 1}^{w_{i}} | \\ = x (- 1)^{k - m + 1} \sum_{j = 1}^{k - m + 1} (- 1)^{j} | D_{k - j + 1}^{u} | \mod h . \end{aligned}$ Note that we used Corollary (1) in the last step. In the future, we will use it without reference. From the above fact it follows that $\begin{aligned} l (u v) & \equiv x - \sum_{i = 1}^{α} l (u w_{i}) \\ \equiv x - x (- 1)^{k - m + 1} \sum_{j = 1}^{k - m + 1} (- 1)^{j} | D_{k - j + 1}^{u} | \\ = x (1 + (- 1)^{k - m + 2} \sum_{j = 1}^{k - m + 1} (- 1)^{j} | D_{k - j + 1}^{u} |) \\ = x ((- 1)^{2 (k - m + 2)} | D_{m - 1}^{u} | + (- 1)^{k - m + 2} \sum_{j = 1}^{k - m + 1} (- 1)^{j} | D_{k - j + 1}^{u} |) \\ = x (- 1)^{k - m + 2} ((- 1)^{k - m + 2} | D_{m - 1}^{u} | + \sum_{j = 1}^{k - m + 1} (- 1)^{j} | D_{k - j + 1}^{u} |) \\ = x (- 1)^{k - m + 2} \sum_{j = 1}^{k - m + 2} (- 1)^{j} | D_{k - j + 1}^{u} |) \\ = x f (u v) \mod h . \end{aligned}$ Thus, by the principal of backwards induction, the statement is true for all $m$ such that $1 \leq m \leq k$ . And so, the statement is true for all edges in trees of even diameter.

Note that this proof does not depend on the fact that the edges and vertices are in a tree of even diameter. Since $f$ is the same for both odd and even diameters with the exception of $c_{1} c_{2}$ , the same proof suffices for all edges in an odd diameter tree except for $c_{1} c_{2}$ , which we now prove separately.

Let $D_{1}^{c_{1}} = {w_{1}, w_{2}, \dots, w_{α}}$ . Since $l$ is an $h$ -magic labeling, $l^{+} (c_{1}) = l (c_{1} c_{2}) + \sum_{i = 1}^{α} l (c_{1} w_{i}) \equiv x \mod h,$ and since $c_{1} w_{i} \in {\hat{D}}_{1}$ for every $1 \leq i \leq α$ , then $l (c_{1} w_{i}) \equiv x f (c_{1} w_{i}) \mod h$ . Thus, $\begin{aligned} \sum_{i = 1}^{α} l (c_{1} w_{i}) & \equiv \sum_{i = 1}^{α} x f (c_{1} w_{i}) \\ = \sum_{i = 1}^{α} x (- 1)^{k} \sum_{j = 1}^{k} (- 1)^{j} | D_{k - j + 1}^{w_{i}} | \\ = x (- 1)^{k} \sum_{j = 1}^{k} (- 1)^{j} | D_{k - j + 1}^{c_{1}} | \mod h . \end{aligned}$ From this, it follows that $\begin{aligned} l (c_{1} c_{2}) & \equiv x - \sum_{i = 1}^{α} l (c_{1} w_{i}) \\ \equiv x (1 + (- 1)^{k + 1} \sum_{j = 1}^{k} (- 1)^{j} | D_{k - j + 1}^{c_{1}} |) \\ = x ((- 1)^{2 (k + 1)} | D_{0}^{c_{1}} | + (- 1)^{k + 1} \sum_{j = 1}^{k} (- 1)^{j} | D_{k - j + 1}^{c_{1}} |) \\ = x (- 1)^{k + 1} ((- 1)^{k + 1} | D_{0}^{c_{1}} | + \sum_{j = 1}^{k} (- 1)^{j} | D_{k - j + 1}^{c_{1}} |) \\ = x (- 1)^{k + 1} \sum_{j = 1}^{k + 1} (- 1)^{j} | D_{k - j + 1}^{c_{1}} | \\ = x f (c_{1} c_{2}) \mod h . \end{aligned}$

Thus, the lemma is true for all edges of an odd diameter tree, and so the proof is done.

This result is significant because it allows us to describe any $h$ -magic labeling of a tree $T_{n}$ . In particular, it tells us that any such labeling is dictated entirely by $x$ , the label of the pendant edges. Thus, determining if a tree $T_{n}$ is $h$ -magic becomes a matter of determining if we can find an $x$ that satisfies the two conditions that $f$ itself does not guarantee. These conditions, again, are that no edge has the label 0 and that $l^{+}$ is also constant for the center vertices. It turns out that being able to find such an $x$ characterizes $h$ -magic graphs.

Theorem 2. $T_{n}$ is $h$ -magic if and only if there exists an integer $x$ with the following two properties.

For every edge $e \in E (T_{n})$ , $\begin{matrix} (2) & x f (e) ≢ 0 \mod h . \end{matrix}$
1. If $n$ is even, then $\begin{matrix} (3) & x \sum_{i = 1}^{k} (- 1)^{k + i} | D_{k - i + 1} | \equiv x \mod h \end{matrix}$
2. If $n$ is odd, then $\begin{matrix} (4) & x \sum_{i = 1}^{k} (- 1)^{i} | D_{k - i + 1}^{c_{1}} | \equiv x \sum_{i = 1}^{k} (- 1)^{i} | D_{k - i + 1}^{c_{2}} | \mod h . \end{matrix}$

Before the proof, we note that the first property corresponds to not allowing the edges to have the label 0, and that the second property corresponds to having the center vertices constant under $l^{+}$ . In particular, the left hand side of (3) will correspond to $l^{+} (c)$ . Similarly, the left hand side of (4) will correspond to $l^{+} (c_{1})$ and the right side to $l^{+} (c_{2})$ . Since $f$ by definition guarantees that $l^{+} (c_{1}) = x$ , equation (4) will suffice to show that $l^{+}$ is constant.

Proof. Assume $T_{n}$ is $h$ -magic and let $l$ be an $h$ -magic labeling. We will demonstrate that if $x$ is the label of the pendant edges under $l$ , then $x$ has both properties. We prove that property 1 holds by contradiction. Assume there exists an edge $e$ such that $x f (e) \equiv 0 \mod h$ . By Lemma 1, $l (e) \equiv 0 \mod h$ too, which contradicts the fact that $l$ is an $h$ -magic labeling. Thus, $x$ has property 1.

For property 2, we start with even diameters. Assume $n = 2 k$ and set $D_{1} = {w_{1}, w_{2}, \dots, w_{α}}$ . By using Lemma 1, we get the result: $\begin{aligned} x & \equiv & l^{+} (c) \\ = & \sum_{i = 1}^{α} l (c w_{i}) \\ \equiv & \sum_{i = 1}^{α} x f (c w_{i}) \\ = & x \sum_{i = 1}^{α} (- 1)^{k} \sum_{j = 1}^{k} (- 1)^{j} | D_{k - j + 1}^{w_{i}} | \\ = & x \sum_{j = 1}^{k} (- 1)^{k + j} | D_{k - j + 1} | \mod h . \end{aligned}$

To prove the odd case, we let $n = 2 k + 1$ and set $D_{1}^{c_{2}} = {w_{1}, w_{2}, \dots, w_{α}}$ . As before, Lemma 1 gives us the result:

$\begin{aligned} x & \equiv l^{+} (c_{2}) \\ = l (c_{1} c_{2}) + \sum_{i = 1}^{α} l (c_{2} w_{i}) \\ \equiv x (- 1)^{k + 1} \sum_{i = 1}^{k + 1} (- 1)^{i} | D_{k - i + 1}^{c_{1}} | + \sum_{i = 1}^{α} x (- 1)^{k} \sum_{j = 1}^{k} (- 1)^{j} | D_{k - j + 1}^{w_{i}} | \\ = x (- 1)^{k} (- \sum_{i = 1}^{k + 1} (- 1)^{i} | D_{k - i + 1}^{c_{1}} | + \sum_{j = 1}^{k} (- 1)^{j} | D_{k - j + 1}^{c_{2}} |) \\ = x (- 1)^{k} (- \sum_{i = 1}^{k} (- 1)^{i} | D_{k - i + 1}^{c_{1}} | + \sum_{j = 1}^{k} (- 1)^{j} | D_{k - j + 1}^{c_{2}} | + (- 1)^{k}) \\ = x (- 1)^{k} (- \sum_{i = 1}^{k} (- 1)^{i} | D_{k - i + 1}^{c_{1}} | + \sum_{j = 1}^{k} (- 1)^{j} | D_{k - j + 1}^{c_{2}} |) + x \mod h . \end{aligned}$ This is equivalent to (4), so $x$ has property 2, and so the forward direction is done.

For the other direction, we first deal with trees of even diameter. Assume that $n = 2 k$ and that there exists an integer $x$ such that (2) and (3) are true. Define $l (e) = x f (e)$ . We claim that $l$ is an $h$ -magic labeling, i.e. that $l^{+} (u) \equiv x \mod h$ for every $u \in V (T_{n})$ , so let $u \in V (T_{n})$ . We split the proof into three cases.

Assume $u \in D_{k}$ . If $v$ is the unique vertex adjacent to $u$ , then, $\begin{aligned} l^{+} (u) & = l (u v) \\ = x f (u v) \\ = - x (- | D_{k}^{u} |) \\ = x . \end{aligned}$

Assume $u \in D_{0}$ , i.e. $u = c$ . If we let $D_{1}^{u} = {w_{1}, w_{2}, \dots, w_{α}}$ , then, $\begin{aligned} l^{+} (u) & = \sum_{i = 1}^{α} l (u w_{i}) \\ = \sum_{i = 1}^{α} x f (u w_{i}) \\ = x \sum_{i = 1}^{α} (- 1)^{k} \sum_{j = 1}^{k} (- 1)^{j} | D_{k - j + 1}^{w_{i}} | \\ = x \sum_{j = 1}^{k} (- 1)^{k + j} | D_{k - j + 1} | \\ \equiv x \mod h . \end{aligned}$

Finally, assume $u \in D_{m}$ where $0 < m < k$ . The proof of Lemma 1 demonstrates that $f (e) = 1$ for every pendant edge. Thus, if $u$ is a pendant vertex, then $l^{+} (u) = x$ . So assume $u$ is not a pendant vertex. Set $v \in D_{m - 1}$ such that $u v \in E (T_{2 k})$ , and $D_{m + 1}^{u} = {w_{1}, w_{2}, \dots, w_{α}}$ . We obtain the result from the following. $\begin{aligned} l^{+} (u) & = l (u v) + \sum_{i = 1}^{α} l (u w_{i}) \\ = x (- 1)^{k - m + 1} \sum_{i = 1}^{k - m + 1} (- 1)^{i} | D_{k - i + 1}^{u} | + x \sum_{i = 1}^{α} (- 1)^{k - m} \sum_{j = 1}^{k - m} (- 1)^{j} | D_{k - j + 1}^{w_{i}} | \\ = x (- 1)^{k - m} (- \sum_{i = 1}^{k - m + 1} (- 1)^{i} | D_{k - i + 1}^{u} | + \sum_{j = 1}^{k - m} (- 1)^{j} | D_{k - j + 1}^{u} |) \\ = x (- 1)^{k - m} (- (- 1)^{k - m + 1} | D_{m}^{u} |) \\ = x . \end{aligned}$

This shows that $l$ is an $h$ -magic labeling, thus completing the proof for even diameter trees. As for trees with odd diameter, let $n = 2 k + 1$ and assume there exists an $x$ such that (2) and (4) hold. As with the even case, define $l (e) = x f (e)$ . The proof for $u \in D_{i}$ for $i > 0$ is the same as in the even case. We deal with $D_{0} = {c_{1}, c_{2}}$ separately. Set $D_{1}^{c_{1}} = {w_{1}, w_{2}, \dots, w_{α}}$ . It follows that $\begin{aligned} l^{+} (c_{1}) & = l (c_{1} c_{2}) + \sum_{i = 1}^{α} l (c_{1} w_{i}) \\ = x (- 1)^{k + 1} \sum_{i = 1}^{k + 1} (- 1)^{i} | D_{k - i + 1}^{c_{1}} | + \sum_{i = 1}^{α} x (- 1)^{k} \sum_{j = 1}^{k} (- 1)^{j} | D_{k - j + 1}^{w_{i}} | \\ = x (- 1)^{k} (- \sum_{i = 1}^{k + 1} (- 1)^{i} | D_{k - i + 1}^{c_{1}} | + \sum_{j = 1}^{k} (- 1)^{j} | D_{k - j + 1}^{c_{1}} |) \\ = x (- 1)^{k} (- (- 1)^{k + 1} | D_{0}^{c_{1}} |) \\ = x . \end{aligned}$

Similarly, if $D_{1}^{c_{2}} = {w_{1}, w_{2}, \dots, w_{α}}$ , then

$\begin{aligned} l^{+} (c_{2}) & = l (c_{1} c_{2}) + \sum_{i = 1}^{α} l (c_{2} w_{i}) \\ = x (- 1)^{k + 1} \sum_{i = 1}^{k + 1} (- 1)^{i} | D_{k - i + 1}^{c_{1}} | + \sum_{i = 1}^{α} x (- 1)^{k} \sum_{j = 1}^{k} (- 1)^{j} | D_{k - j + 1}^{w_{i}} | \\ = x (- 1)^{k} (- \sum_{i = 1}^{k + 1} (- 1)^{i} | D_{k - i + 1}^{c_{1}} | + \sum_{j = 1}^{k} (- 1)^{j} | D_{k - j + 1}^{c_{2}} |) \\ \equiv x (- 1)^{k} (- \sum_{i = 1}^{k + 1} (- 1)^{i} | D_{k - i + 1}^{c_{1}} | + \sum_{j = 1}^{k} (- 1)^{j} | D_{k - j + 1}^{c_{1}} |) \\ = x (- 1)^{k} (- (- 1)^{k + 1} | D_{0}^{c_{1}} |) \\ = x . \end{aligned}$ Thus, $l^{+}$ is constant for all vertices, and so $T_{n}$ is $h$ -magic. This completes the odd case, and so the proof.

Having a complete characterization of when $T_{n}$ is $h$ -magic allows us to find the integer-magic spectrum rather easily. In fact, the proof of Salehi et al. for trees of diameter 5 in [3, 4] gives a template for the proof of our final result. Before going on to the main result, we provide a small and immediate corollary to Theorem 2 that will shed light on the conditions stated in the main result.

Corollary 2. For any $h$ -magic tree of diameter $2 k$ , if $x$ is the label of the pendant edges, then $x \sum_{i = 1}^{k + 1} (- 1)^{k + i} | D_{k - i + 1} | \equiv 0 \mod h .$ Furthermore, for any $h$ -magic tree of diameter $2 k + 1$ , if $x$ is the label of the pendant edges, then $x \sum_{i = 1}^{k} (- 1)^{i} (| D_{k - i + 1}^{c_{1}} | - | D_{k - i + 1}^{c_{2}} |) \equiv 0 \mod h .$

4. The Main Result

The integer-magic spectrum of an arbitrary tree is provided by the following general result.

Theorem 3. Given a tree $T_{n}$ , let $k = f l o o r \frac{n}{2},$ and let $C := {m \in Z : m | r for some r \in Range (f)} .$ When $n$ is even, set $σ := \sum_{i = 1}^{k + 1} (- 1)^{k + i} | D_{k - i + 1} |,$ and when $n$ is odd, set $σ := \sum_{i = 1}^{k} (- 1)^{i} (| D_{k - i + 1}^{c_{1}} | - | D_{k - i + 1}^{c_{2}} |) .$ If $D$ is the set of all positive divisors of $σ$ that are not in $C$ , then $\begin{aligned} I M (T_{n}) = {\begin{array}{cc} \emptyset & if σ \in C; \\ N - C & if σ = 0; \\ ⋃_{d \in D} d N & otherwise. \end{array} \end{aligned}$

Proof. We start by observing, from Corollary 2, that if $x$ is the label of the pendant edges in an $h$ -magic labeling, then $σ x \equiv 0 \mod h$ . Similarly, any integer $x$ with the property that $σ x \equiv 0 \mod h$ also has property 2 in Theorem 2. We now proceed to the cases.

Assume $σ \in C$ , and for a contradiction, assume there is an $h$ such that $T_{n}$ is $h$ -magic. Let $l$ be an $h$ -magic labeling and $x$ be the label of the pendant edges. We then have that $σ x \equiv 0 \mod h$ . Since $σ \in C$ , there exist an edge $e$ such that $σ | f (e)$ , and so $σ x | x f (e)$ . But then, $x f (e) \equiv 0 \mod h$ , so $l (e) \equiv 0 \mod h$ by Lemma 1, which is a contradiction. We conclude $I M (T_{n}) = \emptyset$ .

Assume then that $σ = 0$ . Let $h \in N - C$ . We will prove that $T_{n}$ is $h$ -magic by showing that $x = 1$ satisfies both properties in Theorem 2. From the definition of $C$ , we have that $h ∤ f (e)$ for any edge $e$ . In other words, $f (e) ≢ 0 \mod h$ , so property 1 is satisfied. Furthermore, $σ = 0$ implies property 2. Thus, $T_{n}$ is $h$ -magic, so $h \in I M (T_{n}) .$ For the other direction, assume $h \in I M (T_{n})$ . Let $l$ be an $h$ -magic labeling and $x$ be the label of the pendant edges. Assume for a contradiction that $h | f (e)$ for some edge $e$ . It follows that $x f (e) \equiv 0 \mod h$ , so $l (e) \equiv 0 \mod h$ by Lemma 1, which is a contradiction. We conclude $h ∤ f (e)$ for all edges, so $h \in N - C$ . This proves that $I M (T_{n}) = N - C$ .

Finally, assume that $σ \notin C$ and $σ \neq 0$ . We have to prove that $I M (T_{n}) = ⋃_{d \in D} d N$ . Assume first that $h \in I M (T_{n})$ . Let $l$ be an $h$ -magic labeling and $x$ be the label of the pendant edges. Set $d = g c d (σ, h)$ . We claim that $d \in D$ . By definition, $d | σ$ , so we only need to prove that $d \notin C$ . We do so by contradiction, so assume $d | f (e)$ for some $e \in E (T_{n})$ . From $σ x \equiv 0 \mod h$ , we know $h | σ x$ . But since $d = g c d (σ, h)$ , then $h | d x$ too, and since $d | h$ , it follows that $\frac{h}{d} | x$ . We combine this with $d | f (e)$ to get that $\frac{h}{d} d | x f (e)$ , or $x f (e) \equiv 0 \mod h$ , which is a contradiction with Lemma 1. Thus, $d \notin C$ , so $d \in D$ . And since $d | h$ , there exists a number $p$ such that $d p = h$ , i.e. $h \in ⋃_{d \in D} d N$ .

We prove the other direction. Let $h \in ⋃_{d \in D} d N$ . By definition, $h$ is a multiple of $d \in D$ so set $h = d q$ where $q \in N$ . We will demonstrate that $q = \frac{h}{d}$ is a choice of $x$ that satisfies both properties in Theorem 1. From the definition of $D$ , $d \neq 1$ , so $\frac{h}{d} ≢ 0 \mod h$ . Since $d \notin C$ , $d ∤ f (e)$ for all edges $e$ , or $(\frac{h}{d}) d ∤ \frac{h}{d} f (e)$ . We conclude that $\frac{h}{d} f (e) ≢ 0 \mod h$ for all edges, so property 1 is satisfied. By definition, $d | σ$ , so $\frac{σ}{d} h \equiv 0 \mod h$ . Thus, property 2 is satisfied. By Theorem 2, $T_{n}$ is $h$ -magic, and so $h \in I M (T_{n})$ . In other words, $I M (T_{n}) = ⋃_{d \in D} d N$ , and the proof is done.

References:

G. Chartrand and P. Zhang, 2012. A First Course in Graph Theory, Dover Publications, New York.
Meenakshi, C. and Kathiresan, K.M., 2019. A generalization of magic and antimagic labelings of graphs. AKCE International Journal of Graphs and Combinatorics, 16(2), pp.125-144.
Lee, S.M., Salehi, E. and Sun, H., 2004. Integer-magic spectra of trees with diameters at most four. Journal of Combinatorial Mathematics and Combinatorial Computing, 50, pp.3-16.
Salehi, E. and Bennett, P., 2008. Integer-magic spectra of trees of diameter Five. Journal of Combinatorial Mathematics and Combinatorial Computing, 66, pp.105-111.
Joseph A. G., 2019. A Dynamic Survey in Graphs Labeling (twenty-second edition), The Electronic Journal of Combinatorics (2019), pp.129-132.

[1] G. Chartrand and P. Zhang, 2012. A First Course in Graph Theory, Dover Publications, New York.

[2] Meenakshi, C. and Kathiresan, K.M., 2019. A generalization of magic and antimagic labelings of graphs. AKCE International Journal of Graphs and Combinatorics, 16(2), pp.125-144.

[3] Lee, S.M., Salehi, E. and Sun, H., 2004. Integer-magic spectra of trees with diameters at most four. Journal of Combinatorial Mathematics and Combinatorial Computing, 50, pp.3-16.

[4] Salehi, E. and Bennett, P., 2008. Integer-magic spectra of trees of diameter Five. Journal of Combinatorial Mathematics and Combinatorial Computing, 66, pp.105-111.

[1] Joseph A. G., 2019. A Dynamic Survey in Graphs Labeling (twenty-second edition), The Electronic Journal of Combinatorics (2019), pp.129-132.

Contents

Journal of Combinatorial Mathematics and Combinatorial Computing