# Edge open packing: complexity, algorithmic aspects, and bounds

Boštjan Brešar1,2 and Babak Samadi2
1Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia
2Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

Given a graph $G$, two edges $e_{1},e_{2}\in E(G)$ are said to have a common
edge $e$ if $e$ joins an endvertex of $e_{1}$ to an endvertex of $e_{2}$. A
subset $B\subseteq E(G)$ is an edge open packing set in $G$ if no two edges of
$B$ have a common edge in $G$, and the maximum cardinality of such a set in
$G$ is called the edge open packing number, $\rho_{e}^{o}(G)$, of $G$. In this
paper, we prove that the decision version of the edge open packing number is
NP-complete even when restricted to graphs with universal vertices, Eulerian
bipartite graphs, and planar graphs with maximum degree $4$, respectively. In
contrast, we present a linear-time algorithm that computes the edge open
packing number of a tree. We also resolve two problems posed in the seminal
paper [Edge open packing sets in graphs, RAIRO-Oper. Res. 56 (2022)
3765–3776]. Notably, we characterize the graphs $G$ that attain the upper
bound $\rho_{e}^{o}(G)\leq|E(G)|/\delta(G)$, and provide lower and upper
bounds for the edge-deleted subgraph of a graph and establish the
corresponding realization result.

2020 Mathematical Subject Classification: 05C70, 05C85, 68Q17
Keywords: edge open packing, NP-complete, linear-time algorithm, independent
set.

##  1 Introduction and preliminaries

Throughout this paper, we consider $G$ as a finite simple graph with vertex
set $V(G)$ and edge set $E(G)$. We use [11] as a reference for terminology and
notation which are not explicitly defined here. The (open) neighborhood of a
vertex $v$ is denoted by $N(v)$, and its closed neighborhood is
$N[v]=N(v)\cup\\{v\\}$. The minimum and maximum degrees of $G$ are denoted by
$\delta(G)$ and $\Delta(G)$, respectively. Given the subsets $A,B\subseteq
V(G)$, by $[A,B]$ we denote the set of edges with one endvertex in $A$ and the
other in $B$. If $X\subseteq V(G)$, then $G[X]$ denotes the subgraph of $G$
induced by the vertices of $X$. On the other hand, if $Y\subseteq E(G)$, then
$G[Y]$ denotes the subgraph of $G$ induced by the endvertices of edges in $Y$.

An induced matching $M$ of $G$ is a subset $M\subseteq E(G)$ such that $M$ is
a matching in which no two edges are joined by an edge of $G$. The induced
matching number is the maximum cardinality of an induced matching in $G$. The
problem of finding a maximum induced matching was originally introduced by
Stockmeyer and Vazirani [10] (under the name “risk-free marriage problem”) and
extensively investigated in literature (see, for instance, [1, 4, 8] and
references therein). Unlike for the standard matching problem which is
solvable in polynomial time, it was proved in [10] that the decision version
of the induced matching number is an NP-complete problem. In contrast, a
linear-time algorithm for determining the induced matching number in trees was
found in [12].

Chelladurai et al. [3] introduced the concept of edge open packing in graphs.
A subset $B\subseteq E(G)$ is an edge open packing set (EOP set for short) if
for each pair of edges $e_{1},e_{2}\in B$, there is no edge from $E(G)$
joining an endvertex of $e_{1}$ to an endvertex of $e_{2}$. In other words,
for any two edges $e_{1},e_{2}\in B$, there is no edge $e\in E(G)$ leading to
the existence of a path $e_{1}ee_{2}$ or a triangle $e_{1}ee_{2}e_{1}$ in $G$.
The edge open packing number (EOP number), $\rho_{e}^{o}(G)$, of $G$ is the
maximum cardinality of an EOP set in $G$. We observe that if $B$ is an EOP set
(resp. induced matching) of $G$, then $G[B]$ is a disjoint union of induced
stars (resp. $K_{1,1}$-stars). In this sense, the problem of induced matching
can be considered as a variation of the EOP problem. Note that an EOP set is
not necessarily a matching, let alone an induced matching.

An injective $k$-edge coloring of a graph $G$ is an assignment of colors
(integers) from $\\{1,\ldots,k\\}$ to the edges of $G$ such that any two edges
$e_{1},e_{2}\in E(G)$ having a common edge (that is an edge $e$ with one
endvertex common with $e_{1}$ and the other endvertex common with $e_{2}$)
receive different colors. The minimum number $k$ of colors required for an
injective edge coloring is called the injective chromatic index of $G$,
denoted by $\chi^{\prime}_{i}(G)$. The study of this concept was initiated by
Cardoso et al. in [2] and investigated in [5, 9] among others. We observe that
the color classes of an injective edge coloring of a graph $G$ are the very
EOP sets of $G$. In fact, the problem of injective edge coloring amounts to
the problem of edge partitioning of a graph into EOP sets. Some real-world
applications of these two concepts are given in [2] and [3], respectively. In
the only paper so far concerned with EOP sets and numbers [3], the complexity
and algorithmic issues have not been considered. In this paper, we fill this
gap by proving three different NP-completeness results in specific families of
graphs and constructing a linear-time algorithm resolving the problem in
trees.

Section 2 of this paper pertains to the study of computational complexity of
the EOP problem. We prove that the decision problem associated with
$\rho_{e}^{o}$ is NP-complete even when restricted to three special families
of graphs, namely, graphs with universal vertices, Eulerian bipartite graphs,
and planar graphs with maximum degree $4$. In Section 3, we prove that the EOP
number $\rho_{e}^{o}(T)$ and an optimal EOP set for any tree $T$ can be
computed/constructed in linear time by exhibiting an efficient algorithm for
EOP in trees. A version of dynamic programming is used, where four auxiliary
parameters, versions of the EOP number, are being computed. Finally, in
Section $4$, we solve two problems posed in [3]. Firstly, we provide a
structural characterization of all graphs $G$ attaining the previously proved
upper bound $\rho_{e}^{o}(G)\leq|E(G)|/\delta(G)$. Secondly, we analyze the
effect of edge removal on the EOP number of a graph $G$, obtaining a lower and
an upper bound for $\rho_{e}^{o}(G-e)$, where $e$ is an edge of $G$. We also
show that all possible values between the bounds can be realized by a graph
and some of its edges.

By a $\rho_{e}^{o}(G)$-set and an $\alpha(G)$-set we represent an EOP set and
an independent set of $G$ of cardinality $\rho_{e}^{o}(G)$ and $\alpha(G)$,
respectively, where $\alpha(G)$ stands for the independence number of $G$.

##  2 Computational complexity

We discuss the problem of deciding whether for a given graph $G$ and a
positive integer $k$ the graph $G$ has the EOP number at least $k$. We state
it as the following decision problem.

Edge open packing problem
---
Instance: A graph $G$ and an integer $k\leq|E(G)|$.
Question: Is $\rho_{e}^{o}(G)\geq k$?
(1)

In order to study the complexity of the problem (1), we make use of the
Independent Set Problem which is known to be NP-complete [6].

Independent Set Problem
---
Instance: A graph $G$ and an integer $j\leq|V(G)|$.
Question: Is $\alpha(G)\geq j$?

As an immediate consequence of the following theorem we deduce that the
problem (1) is NP-complete for graphs of diameter $2$.

######  Theorem 2.1.

Edge Open Packing Problem is NP-complete even for graphs with universal
vertices.

###### Proof.

The problem clearly belongs to NP because checking that a given subset of
edges is indeed an EOP set of cardinality at least $k$ can be done in
polynomial time.

Suppose that $G$ is a graph of order $n$ and size $m$. We set $k=m+n+j$. Let
$H$ be obtained from $G$ by adding the new vertices
$v,u_{1},u_{2},\dots,u_{m+n}$ and joining $v$ to all vertices in
$V(G)\cup\\{u_{1},u_{2},\dots,u_{m+n}\\}$. It is easy to observe that the
construction of the graph $H$ can be accomplished in polynomial time and that
$H$ has the universal vertex $v$. Let $I$ be an $\alpha(G)$-set. Since
$J=I\cup\\{u_{1},u_{2},\dots,u_{m+n}\\}$ is an independent set in $H$, it is
easily observed that $B=\\{vw\in E(H):\,w\in J\\}$ is an EOP in $H$.
Therefore, $\rho_{e}^{o}(H)\geq|B|=m+n+\alpha(G)$.

Let $B^{\prime}$ be a $\rho_{e}^{o}(H)$-set. Suppose first that
$B^{\prime}\cap E(G)\neq\emptyset$ and that $xy\in B^{\prime}\cap E(G)$. If
there exists an edge $vu_{r}\in B^{\prime}$ for some $1\leq r\leq m+n$, then
we have the path $u_{r}vxy$ in which $u_{r}v,xy\in B^{\prime}$, which is
impossible. Therefore, $B^{\prime}\cap\\{vu_{i}:\,1\leq i\leq
m+n\\}=\emptyset$. This, in particular, implies that
$|B^{\prime}|\leq|E(H)\setminus\\{vu_{i}:\,1\leq i\leq
m+n\\}|=m+n<m+n+\alpha(G)$, a contradiction. Hence, $B^{\prime}\cap
E(G)=\emptyset$.

Suppose that $|B^{\prime}\cap\\{vw\in E(H):\,w\in V(G)\\}|>\alpha(G)$ and
$vw_{1},\dots,vw_{\alpha(G)+1}\in B^{\prime}\cap\\{vw\in E(H):\,w\in V(G)\\}$.
Clearly, there exists an edge $w_{r}w_{s}\in E(G)$ for some $1\leq r\neq
s\leq\alpha(G)+1$. This, in turn, leads to the triangle $vw_{r}w_{s}v$. So,
the edges $vw_{r}$ and $vw_{s}$ have the common edge $w_{r}w_{s}$, which is a
contradiction. This implies that $|B^{\prime}\cap\\{vw\in E(H):\,w\in
V(G)\\}|\leq\alpha(G)$, and hence $\rho_{e}^{o}(H)=|B^{\prime}|\leq
m+n+\alpha(G)$. This shows that $\rho_{e}^{o}(H)=m+n+\alpha(G)$.

Our reduction is now completed by taking into account the fact that
$\rho_{e}^{o}(H)\geq k$ if and only if $\alpha(G)\geq j$. Since Independent
Set Problem is NP-complete, we have the same for Edge Open Packing Problem
restricted to the family of graphs with universal vertices. ∎

In spite of the fact that Independent Set Problem is solvable in polynomial
time for bipartite graphs, Edge open packing problem remains NP-complete for a
subfamily of bipartite graphs. In this sense, one might even say that it is
harder than Independent Set Problem.

######  Theorem 2.2.

Edge Open Packing Problem is NP-complete even for Eulerian bipartite graphs.

###### Proof.

We need to prove that the problem is NP-hard as we already proved that it is
in NP. Let $G$ be any graph with vertex set $\\{v_{1},\ldots,v_{n}\\}$ and
size $m$. We construct the graph $H_{G}$ derived from $G$ as follows. For each
vertex $v_{i}\in V(G)$, take two vertices $v_{i}$ and $v_{i}^{\prime}$ and
connect them by an edge, and for each edge $v_{i}v_{j}\in E(G)$ add six paths,
three of which connecting $v_{i}$ and $v_{j}^{\prime}$ and the other three
connecting $v_{i}^{\prime}$ and $v_{j}$ as follows:

$P_{ij}^{1}:v_{i}x_{ij}\widetilde{x_{ij}}x_{ji}^{\prime\prime}x_{ji}^{\prime}v_{j}^{\prime}$,
$P_{ij}^{2}:v_{i}y_{ij}\widetilde{y_{ij}}y_{ji}^{\prime\prime}y_{ji}^{\prime}v_{j}^{\prime}$,
$P_{ij}^{1}:v_{i}z_{ij}\widetilde{z_{ij}}z_{ji}^{\prime\prime}z_{ji}^{\prime}v_{j}^{\prime}$

$P_{ji}^{1}:v_{i}^{\prime}x_{ij}^{\prime}x_{ij}^{\prime\prime}\widetilde{x_{ji}}x_{ji}v_{j}$,
$P_{ji}^{2}:v_{i}^{\prime}y_{ij}^{\prime}y_{ij}^{\prime\prime}\widetilde{y_{ji}}y_{ji}v_{j}$,
$P_{ji}^{3}:v_{i}^{\prime}z_{ij}^{\prime}z_{ij}^{\prime\prime}\widetilde{z_{ji}}z_{ji}v_{j}$.

It is clear that $|V(H_{G})|=2n+24m$, $|E(H_{G})|=n+30m$ and that the
construction of $H_{G}$ can be accomplished in polynomial time. Moreover, it
is evident by the structure that $H_{G}$ is bipartite (a local induced
subgraph of the graph $H_{G}$ is depicted in Figure 1).

Let $I$ be an $\alpha(G)$-set. If one of the endvertices of $v_{i}v_{j}\in
E(G)$, say $v_{j}$, belongs to $I$, then let

$A_{ij}=\\{v_{j}v_{j^{\prime}}\\}\cup\\{v_{j}x_{ji},v_{j}y_{ji},v_{j}z_{ji},x_{ij}^{\prime\prime}x_{ij}^{\prime},y_{ij}^{\prime\prime}y_{ij}^{\prime},z_{ij}^{\prime\prime}z_{ij}^{\prime}\\}\cup\\{x_{ij}\widetilde{x_{ij}},\widetilde{x_{ij}}x_{ji}^{\prime\prime},y_{ij}\widetilde{y_{ij}},\widetilde{y_{ij}}y_{ji}^{\prime\prime},z_{ij}\widetilde{z_{ij}},\widetilde{z_{ij}}z_{ji}^{\prime\prime}\\}.$

Otherwise, let

$A_{ij}=\\{x_{ij}\widetilde{x_{ij}},\widetilde{x_{ij}}x_{ji}^{\prime\prime},y_{ij}\widetilde{y_{ij}},\widetilde{y_{ij}}y_{ji}^{\prime\prime},z_{ij}\widetilde{z_{ij}},\widetilde{z_{ij}}z_{ji}^{\prime\prime}\\}\cup\\{x_{ij}^{\prime}x_{ij}^{\prime\prime},x_{ij}^{\prime\prime}\widetilde{x_{ji}},y_{ij}^{\prime}y_{ij}^{\prime\prime},y_{ij}^{\prime\prime}\widetilde{y_{ji}},z_{ij}^{\prime}z_{ij}^{\prime\prime},z_{ij}^{\prime\prime}\widetilde{z_{ji}}\\}.$

It is then readily checked that $\bigcup_{v_{i}v_{j}\in E(G)}A_{ij}$ is an EOP
set of $H_{G}$, and hence

$\rho_{e}^{o}(H_{G})\geq|\cup_{v_{i}v_{j}\in E(G)}A_{ij}|=12m+\alpha(G).$ (2)

$v_{i}^{\prime}$$v_{i}$$v_{j}^{\prime}$$v_{j}$$y_{ij}$$\widetilde{y_{ij}}$$y_{ji}^{\prime\prime}$$y_{ji}^{\prime}$$y_{ij}^{\prime}$$y_{ij}^{\prime\prime}$$\widetilde{y_{ji}}$$y_{ji}$$x_{ij}$$\widetilde{x_{ij}}$$x_{ji}^{\prime\prime}$$x_{ji}^{\prime}$$z_{ij}$$\widetilde{z_{ij}}$$z_{ji}^{\prime\prime}$$z_{ji}^{\prime}$$x_{ij}^{\prime}$$x_{ij}^{\prime\prime}$$\widetilde{x_{ji}}$$x_{ji}$$z_{ji}$$\widetilde{z_{ji}}$$z_{ij}^{\prime\prime}$$z_{ij}^{\prime}$
Figure 1: The subgraph of $H_{G}$ corresponding to the adjacent vertices
$v_{i}$ and $v_{j}$ of $G$.

For the proof of the reversed inequality, let $B$ be a
$\rho_{e}^{o}(H_{G})$-set. We have

$\rho_{e}^{o}(H_{G})=|B|=\sum_{v_{i}v_{j}\in
E(G)}\Big{|}B\cap\Big{(}\bigcup_{k=1}^{3}\big{(}E(P_{ij}^{k})\cup
E(P_{ji}^{k})\big{)}\Big{)}\Big{|}+\Big{|}B\cap\\{v_{i}v_{i}^{\prime}:\,v_{i}\in
V(G)\\}\Big{|}.$ (3)

By the structure of $H_{G}$ and the definition of an EOP set, we observe that
$\big{|}B\cap\big{(}\bigcup_{k=1}^{3}(E(P_{ij}^{k})\cup
E(P_{ji}^{k}))\big{)}\big{|}$ does not exceed $12$ for each $v_{i}v_{j}\in
E(G)$. To see this, note that the vertices of any two distinct paths
$P_{ij}^{k}$ (as well as those of any two distinct paths $P_{ij}^{\ell}$)
induce the cycle $C_{10}$, for which it is easily seen that
$\rho_{e}^{o}(C_{10})=4$. In addition, adding the third path between $v_{i}$
and $v_{j}^{\prime}$, obtaining the subgraph induced by
$\cup_{k=1}^{3}V(P_{ij}^{k})$, we can only add two more edges to an EOP set of
this subgraph, which yields the above-mentioned upper bound $12$.

Next, we define three subsets of $E(G)$, namely

$E_{k}=\\{v_{i}v_{j}\in E(G):\
|\\{v_{i}v_{i}^{\prime},v_{j}v_{j}^{\prime}\\}\cap B|=k\\}$

for $k\in\\{0,1,2\\}$. Clearly, $E_{0}$, $E_{1}$ and $E_{2}$ are pairwise
disjoint, and $E(G)=E_{0}\cup E_{1}\cup E_{2}$. We then, in view of (3), have

$\begin{array}[]{lcl}\rho_{e}^{o}(H_{G})=|B|&=&\sum\limits_{\begin{subarray}{c}v_{i}v_{j}\in
E_{0}\end{subarray}}\Big{|}B\cap\Big{(}\bigcup_{k=1}^{3}\big{(}E(P_{ij}^{k})\cup
E(P_{ji}^{k})\big{)}\Big{)}\Big{|}\\\ &+&\sum\limits_{v_{i}v_{j}\in
E_{1}}\Big{|}B\cap\Big{(}\bigcup_{k=1}^{3}\big{(}E(P_{ij}^{k})\cup
E(P_{ji}^{k})\big{)}\Big{)}\Big{|}\\\ &+&\sum\limits_{v_{i}v_{j}\in
E_{2}}\Big{|}B\cap\Big{(}\bigcup_{k=1}^{3}\big{(}E(P_{ij}^{k})\cup
E(P_{ji}^{k})\big{)}\Big{)}\Big{|}+\Big{|}B\cap\\{v_{i}v_{i}^{\prime}:\,v_{i}\in
V(G)\\}\Big{|}.\end{array}$ (4)

It is not difficult to verify (see also Figure 1) that
$\big{|}B\cap\big{(}\bigcup_{k=1}^{3}\big{(}E(P_{ij}^{k})\cup
E(P_{ji}^{k})\big{)}\big{)}\big{|}\leq 12$ if $v_{i}v_{j}\in E_{0}\cup E_{1}$,
and $\big{|}B\cap\big{(}\bigcup_{k=1}^{3}\big{(}E(P_{ij}^{k})\cup
E(P_{ji}^{k})\big{)}\big{)}\big{|}\leq 9$ if $v_{i}v_{j}\in E_{2}$. So, in
view of (4), we have

$\rho_{e}^{o}(H_{G})=|B|\leq
12|E_{0}|+12|E_{1}|+9|E_{2}|+|B\cap\\{v_{i}v_{i}^{\prime}:\,v_{i}\in
V(G)\\}|.$ (5)

Let $W=V(G[E_{2}])$. Note that $G[E_{2}]$ has no isolated vertices if
$W\neq\emptyset$, and so $2|E_{2}|\geq|W|$. On the other hand, let
$R=\\{v_{i}\in V(G):\,v_{i}v_{i}^{\prime}\in B\\}\setminus W$. Note that $R$
is an independent set in $G$. Clearly,
$|B\cap\\{v_{i}v_{i}^{\prime}:\,v_{i}\in V(G)\\}|$=$|W|+|R|$. Inserting this
to (5), we get

$\rho_{e}^{o}(H_{G})=|B|\leq 12|E_{0}|+12|E_{1}|+9|E_{2}|+|W|+|R|\leq
12|E_{0}|+12|E_{1}|+11|E_{2}|+\alpha(G),$

which is strictly less than $12m+\alpha(G)$ unless $E_{2}=\emptyset$. Due to
(2), we infer that $E_{2}=\emptyset$. This implies that
$B\cap\\{v_{i}v_{i}^{\prime}:\,v_{i}\in V(G)\\}$ is an independent set, which
again from (5) yields

$\rho_{e}^{o}(H_{G})=|B|\leq
12|E_{0}|+12|E_{1}|+|B\cap\\{v_{i}v_{i}^{\prime}:\,v_{i}\in V(G)\\}|\leq
12m+\alpha(G),$

as desired. Hence, we have the equality $\rho_{e}^{o}(H_{G})=12m+\alpha(G)$ by
(2).

Setting $k=12m+j$, the reduction is completed as $\rho_{e}^{o}(H_{G})\geq k$
if and only if $\alpha(G)\geq j$. Note that if $G$ is a connected cubic graph,
then ($i$) $H_{G}$ is a connected bipartite graph and ($ii$) all vertices of
$H_{G}$ are of even degree ($2n$ vertices are of degree 10 and the rest are of
degree 2). This shows that $H_{G}$ is an Eulerian graph. Now, since
Independent Set Problem is NP-complete even for (connected) cubic graphs (see
[7]), we have the same with Edge Open Packing Problem for Eulerian bipartite
graphs. This completes the proof. ∎

In contrast to the family of graphs with maximum degree as large as possible
(for which the decision problem (1) is NP-complete due to Theorem 2.1), the
problem remains NP-complete for some special classes of sparse graphs.

######  Theorem 2.3.

Edge Open Packing Problem is NP-complete even when restricted to planar graphs
of maximum degree at most $4$.

###### Proof.

We only need to prove the NP-hardness of the problem. Let $G$ be a graph with
$V(G)=\\{v_{1},\dots,v_{n}\\}$. For every $1\leq i\leq n$, consider a path
$P_{i}:x_{i}z_{i}y_{i}$. Let $G^{\prime}$ be obtained from $G$ by joining
$z_{i}$ to $v_{i}$ for each $1\leq i\leq n$. Note that $G^{\prime}$ is planar
if and only if $G$ is planar. Suppose that $B^{\prime}$ is a
$\rho_{e}^{o}(G^{\prime})$-set. Let $H$ be the subgraph of $G^{\prime}$
induced by $B^{\prime}\cap E(G)$. If $H$ is the null graph (that is, a graph
whose vertex set and edge set are empty), then
$B^{\prime}\subseteq\bigcup_{i=1}^{n}E_{i}$, where
$E_{i}=\\{z_{i}x_{i},z_{i}y_{i},z_{i}v_{i}\\}$. Set $A=\\{v_{i}\in
V(G):\,z_{i}v_{i}\in B^{\prime}\\}$. Since $B^{\prime}$ is an EOP set in
$G^{\prime}$, it follows that $A$ is an independent set in $G$. We then get

$\rho_{e}^{o}(G^{\prime})=\big{|}B^{\prime}\cap\big{(}\bigcup_{i=1}^{n}E_{i}\big{)}\big{|}=\sum_{v_{i}\in
A}|B^{\prime}\cap E_{i}|+\sum_{v_{i}\notin A}|B^{\prime}\cap E_{i}|\leq
3|A|+2(n-|A|)\leq 2n+\alpha(G).$

Suppose now that $H$ is not the null graph. By the definition of an EOP set,
$H$ is the disjoint union of some induced stars
$K_{1,n_{1}},\ldots,K_{1,n_{r}}$ with centers $v_{i_{1}},\ldots,v_{i_{r}}$,
respectively (if one of the stars is isomorphic to $K_{2}$, then we consider
only one of its vertices as the center). Since $B^{\prime}$ is a maximum EOP
set in $G^{\prime}$, it necessarily follows that
$E(K_{1,n_{t}})\cup\\{v_{i_{t}}z_{i_{t}}\\}\subseteq B^{\prime}$ for all
$1\leq t\leq r$. On the other hand, by the definition, $Q=\\{v_{i}\in
V(G):\,E_{i}\subseteq B^{\prime}\\}$ is an independent set in $G$. Moreover,
there is no vertex in $Q$ adjacent to a vertex in
$\bigcup_{i=1}^{r}(V(K_{1,n_{i}})\setminus\\{v_{n_{i}}\\})$. This in
particular implies that $|Q|+\sum_{t=1}^{r}n_{t}\leq\alpha(G)$. We now have

$\rho_{e}^{o}(G^{\prime})=|B^{\prime}|\leq
3|Q|+\sum_{t=1}^{r}n_{t}+r+2(n-|Q|-\sum_{t=1}^{r}n_{t}-r)=|Q|+2n-\sum_{t=1}^{r}n_{t}-r<2n+\alpha(G).$

In either case, we have proved that $\rho_{e}^{o}(G^{\prime})\leq
2n+\alpha(G)$.

On the other hand, let $I$ be an $\alpha(G)$-set. We observe that
$A^{\prime}=(\bigcup_{v_{i}\in I}E_{i})\cup(\bigcup_{v_{i}\notin
I}\\{x_{i}z_{i},y_{i}z_{i}\\})$ is an EOP set in $G^{\prime}$. Hence,
$\rho_{e}^{o}(G^{\prime})\geq|A^{\prime}|=2n+\alpha(G)$. This leads to the
desired equality $\rho_{e}^{o}(G^{\prime})=2n+\alpha(G)$

Our reduction is completed by taking $\rho_{e}^{o}(G^{\prime})\geq k$ if and
only if $\alpha(G)\geq j$ into account, where $k=j+2n$. Because Independent
Set Problem is NP-complete for planar graphs of maximum degree $3$ (see [7]),
$\Delta(G^{\prime})=\Delta(G)+1$, and the fact that $G^{\prime}$ is planar if
$G$ is planar, we have the NP-completeness of Edge Open Packing Problem for
planar graphs with maximum degree $4$. ∎

##  3 An efficient algorithm for edge open packing in trees

We will use the following notation throughout this section. Let $T$ be a tree.
Arbitrarily choose a vertex $r$, making $T$ a rooted tree with root $r$. For
every $v\in V(T)$, let $T_{v}$ denote the rooted subtree of $T$ induced by
$v$, as its root, along with all descendants of $v$ in $T$. In particular,
$T_{r}$ is isomorphic to $T$ with $r$ as its root. For every $v\in V(T)$, let
$C(v)$ denote the set of children of $v$ in $T$.

We need the following versions of optimal EOP sets in a (rooted) tree.

  * •

$\rho_{e}^{o}(T_{v})=\max\\{|S|:\,S\textrm{ is an EOP set in }T_{v}\\}$;
(This is the standard EOP number of the subtree $T_{v}$. In particular,
$\rho_{e}^{o}(T_{r})=\rho_{e}^{o}(T)$.)

  * •

$\rho^{c}(T_{v})=\max\\{|S|:\,S\textrm{ is an EOP set in }T_{v}\textrm{, where
}v\textrm{ is the center of a star in }T_{v}[S]\\}$;

  * •

$\rho^{\ell}(T_{v})=\max\\{|S|:\,S\textrm{ is an EOP set in }T_{v}\textrm{,
where }v\textrm{ is a leaf of a star in }T_{v}[S]\\}$;

  * •

$\rho^{\prime}(T_{v})=\max\\{|S|:\,S\textrm{ is an EOP set in }T_{v}\textrm{,
where }v\textrm{ is not in }V(T_{v}[S])\\}$;
(This is the maximum cardinality of an EOP set $S$ in $T_{v}$ in which $v$ is
not incident with an edge of $S$.)

  * •

$\rho^{\prime\prime}(T_{v})=\max\\{|S|:\,S\textrm{ is an EOP set in
}T_{v}\textrm{, where }N[v]\cap V(T_{v}[S])=\emptyset\\}$
(This is the maximum cardinality of an EOP set $S$ in $T_{v}$ such that
neither $v$ nor any of its children is incident with an edge of $S$.).

Since every EOP set that appears in the definition of
$\rho^{\prime\prime}(T_{v})$ also satisfies the conditions from the definition
of $\rho^{\prime}(T_{v})$, we immediately infer the following relation:

$\rho^{\prime}(T_{v})\geq\rho^{\prime\prime}(T_{v})\ \mbox{for each}\ v\in
V(T).$ (6)

We next state a basic and important remark, which follows from the fact that
in an arbitrary EOP set $S$ of $T_{v}$ one of the following possibilities
occurs: $(i)$ $v$ is the center of a star from $T_{v}[S]$, $(ii)$ $v$ is a
leaf of a star from $T_{v}[S]$, or $(iii)$ $v$ is not incident with an edge
from $S$. (If $v$ belongs to a $K_{1,1}$-component of $T_{v}[S]$, then we may
consider $v$ either as the leaf or as the center of the corresponding star
$K_{1,1}$.)

######  Observation 3.1.

If $T$ is a (rooted) tree and $v\in V(T)$, then

$\rho_{e}^{o}(T_{v})=\max\\{\rho^{c}(T_{v}),\rho^{\ell}(T_{v}),\rho^{\prime}(T_{v})\\}.$

From the above observation, one might think that the parameter
$\rho^{\prime\prime}(T_{v})$ is not needed, yet it turns out that the
calculations are easier if we consider it as well. Note that if $v$ is a leaf
of the tree $T$, then $\rho_{e}^{o}(T_{v})=0$, and so all four parameters are
also $0$. For a further simple example, consider the case when $C(v)$ consists
only of leaves (and so $T_{v}$ is a star). Then,
$\rho_{e}^{o}(T_{v})=\rho^{c}(T_{v})=|C(v)|$, while $\rho^{\ell}(T_{v})=1$ and
$\rho^{\prime}(T_{v})=\rho^{\prime\prime}(T_{v})=0$.

Now we will calculate
$\rho^{c}(T_{v}),\rho^{\ell}(T_{v}),\rho^{\prime}(T_{v})$ and
$\rho^{\prime\prime}(T_{v})$ by using the values of the parameters in vertices
from $C(v)$.

For calculating $\rho^{c}(T_{v})$, we need to define two types of vertices $u$
with respect to the values of $\rho^{\prime}$ and $\rho^{\prime\prime}$ of the
corresponding subtrees $T_{u}$. Let $u\in V(T)$. If

$\rho^{\prime\prime}(T_{u})+1\geq\rho^{\prime}(T_{u}),$

then $u$ is of Type 1; otherwise $u$ is of Type 2.

######  Lemma 3.2.

For the rooted tree $T$ and $v\in V(T)$,

$\rho^{c}(T_{v})=\left\\{\begin{array}[]{ll}\sum\limits_{\begin{subarray}{c}u\in
C(v),\\\ u\textrm{ Type
1}\end{subarray}}{\hskip-10.0pt(\rho^{\prime\prime}(T_{u})+1)}\,\,+\sum\limits_{\begin{subarray}{c}u\in
C(v),\\\ u\textrm{ Type
2}\end{subarray}}{\hskip-8.0pt\rho^{\prime}(T_{u})}&\textrm{if there is some
}u\in C(v)\textrm{ of Type 1},\\\ \\\ \sum\limits_{u\in
C(v)}{\hskip-8.0pt\rho^{\prime}(T_{u})}+\min\limits_{u\in
C(v)}\\{\rho^{\prime\prime}(T_{u})+1-\rho^{\prime}(T_{u})\\}&\textrm{if all
}u\in C(v)\textrm{ are of Type 2}.\end{array}\right.$

###### Proof.

Let $S$ be an EOP set of $T_{v}$, which satisfies the conditions from the
definition of $\rho^{c}(T_{v})$. That is, $v$ is the center of a star $R$ in
$T_{v}[S]$. Therefore, at least one vertex in $C(v)$ is a leaf of the star
$R$. Let $C^{\prime}\subseteq C(v)$ be the set of leaves from $R$, while
$C^{\prime\prime}=C(v)\setminus C^{\prime}$ (it is possible that
$C^{\prime\prime}=\emptyset$). For each $u\in C(v)$, let $S_{u}=S\cap
E(T_{u})$. Note that

$|S|=|C^{\prime}|+\sum_{u\in C(v)}{|S_{u}|}.$

Let $u\in C^{\prime}$. Because $v$ is the center of the star $R$ in $T_{v}[S]$
and since $uv\in S$, neither $u$ nor any of the children of $u$ in $T_{u}$ can
be incident with an edge in $S_{u}$. We infer that
$|S_{u}|\leq\rho^{\prime\prime}(T_{u})$. On the other hand, if $u\in
C^{\prime\prime}$, then $u$ cannot be incident with an edge in $S_{u}$, yet
its children may be. Therefore, $|S_{u}|\leq\rho^{\prime}(T_{u})$ in this
case.

First, assume that there exists a vertex in $C(v)$ of Type 1. Now, if $u\in
C^{\prime\prime}$ is of Type 1, then
$|S_{u}|\leq\rho^{\prime}(T_{u})\leq\rho^{\prime\prime}(T_{u})+1$. Similarly,
if $u\in C^{\prime}$ is of Type 2, then
$|S_{u}|\leq\rho^{\prime\prime}(T_{u})<\rho^{\prime}(T_{u})-1$. Thus,

$\begin{array}[]{lll}|S|&=&|C^{\prime}|+\hskip-10.0pt\sum\limits_{\begin{subarray}{c}u\in
C^{\prime},\\\ u\textrm{ Type
1}\end{subarray}}{\hskip-10.0pt|S_{u}|}+\sum\limits_{\begin{subarray}{c}u\in
C^{\prime},\\\ u\textrm{ Type
2}\end{subarray}}{\hskip-10.0pt|S_{u}|}+\sum\limits_{\begin{subarray}{c}u\in
C^{\prime\prime},\\\ u\textrm{ Type
1}\end{subarray}}{\hskip-10.0pt|S_{u}|}+\sum\limits_{\begin{subarray}{c}u\in
C^{\prime\prime},\\\ u\textrm{ Type 2}\end{subarray}}{\hskip-10.0pt|S_{u}|}\\\
\\\ &\leq&|C^{\prime}|+\hskip-10.0pt\sum\limits_{\begin{subarray}{c}u\in
C^{\prime},\\\ u\textrm{ Type
1}\end{subarray}}{\hskip-10.0pt\rho^{\prime\prime}(T_{u})}+\sum\limits_{\begin{subarray}{c}u\in
C^{\prime},\\\ u\textrm{ Type
2}\end{subarray}}{\hskip-10.0pt(\rho^{\prime}(T_{u})-2)}+\sum\limits_{\begin{subarray}{c}u\in
C^{\prime\prime},\\\ u\textrm{ Type
1}\end{subarray}}{\hskip-10.0pt(\rho^{\prime\prime}(T_{u})+1)}+\sum\limits_{\begin{subarray}{c}u\in
C^{\prime\prime},\\\ u\textrm{ Type
2}\end{subarray}}{\hskip-10.0pt\rho^{\prime}(T_{u})}\\\ \\\
&=&\hskip-10.0pt\sum\limits_{\begin{subarray}{c}u\in C^{\prime},\\\ u\textrm{
Type
1}\end{subarray}}{\hskip-10.0pt(\rho^{\prime\prime}(T_{u})+1)}+\sum\limits_{\begin{subarray}{c}u\in
C^{\prime},\\\ u\textrm{ Type
2}\end{subarray}}{\hskip-10.0pt(\rho^{\prime}(T_{u})-1)}+\sum\limits_{\begin{subarray}{c}u\in
C^{\prime\prime},\\\ u\textrm{ Type
1}\end{subarray}}{\hskip-10.0pt(\rho^{\prime\prime}(T_{u})+1)}+\sum\limits_{\begin{subarray}{c}u\in
C^{\prime\prime},\\\ u\textrm{ Type
2}\end{subarray}}{\hskip-10.0pt\rho^{\prime}(T_{u})}.\\\ \end{array}$

and the above expression is in turn less than of equal to

$\sum\limits_{\begin{subarray}{c}u\in C(v),\\\ u\textrm{ Type
1}\end{subarray}}{\hskip-10.0pt(\rho^{\prime\prime}(T_{u})+1)}\,\,+\sum\limits_{\begin{subarray}{c}u\in
C(v),\\\ u\textrm{ Type 2}\end{subarray}}{\hskip-8.0pt\rho^{\prime}(T_{u})}.$

Second, assume that all vertices in $C(v)$ are of Type 2. Then,

$\begin{array}[]{lll}|S|&\leq&|C^{\prime}|+\hskip-6.0pt\sum\limits_{\begin{subarray}{c}u\in
C^{\prime},\\\ u\textrm{ Type
2}\end{subarray}}{\hskip-10.0pt\rho^{\prime\prime}(T_{u})}+\sum\limits_{\begin{subarray}{c}u\in
C^{\prime\prime},\\\ u\textrm{ Type
2}\end{subarray}}{\hskip-10.0pt\rho^{\prime}(T_{u})}\\\ \\\
&=&\hskip-6.0pt\sum\limits_{\begin{subarray}{c}u\in C^{\prime},\\\ u\textrm{
Type
2}\end{subarray}}{\hskip-10.0pt(\rho^{\prime\prime}(T_{u})+1)}+\sum\limits_{\begin{subarray}{c}u\in
C^{\prime\prime},\\\ u\textrm{ Type
2}\end{subarray}}{\hskip-10.0pt\rho^{\prime}(T_{u})}\\\ \\\
&\leq&\sum\limits_{u\in
C(v)}{\hskip-8.0pt\rho^{\prime}(T_{u})}+\min\limits_{u\in
C(v)}\\{\rho^{\prime\prime}(T_{u})+1-\rho^{\prime}(T_{u})\\},\end{array}$

where the latter inequality holds because
$\rho^{\prime}(T_{u})>\rho^{\prime\prime}(T_{u})+1$ for all $u\in C(v)$ and
since $|C^{\prime}|>0$. All in all, we have proved that $\rho^{c}(T_{v})$
cannot be larger than the expression on the right side of the equality stated
in the lemma.

For the reverse inequalities, we also consider two cases. Suppose that there
exists $u\in C(v)$ such that
$\rho^{\prime\prime}(T_{u})+1\geq\rho^{\prime}(T_{u})$ (that is, $u$ is of
Type 1). Let $B$ be an EOP set of $T_{v}$, where $v$ is the center of a star
in $T_{v}[B]$, such that $vu\in B$ if and only if $u$ is of Type 1, while
$T_{u}[B]$ depends on the type of $u\in C(v)$. That is, if $u$ is of Type 1,
then let $E(T_{u}[B])$ be a $\rho^{\prime\prime}(T_{u})$-set, and if $u$ is of
Type 2, then let $E(T_{u}[B])$ be a $\rho^{\prime}(T_{u})$-set. Therefore, the
inequality

$\rho^{c}(T_{v})\geq|B|=\sum\limits_{\begin{subarray}{c}u\in C(v),\\\
u\textrm{ Type
1}\end{subarray}}{\hskip-10.0pt(\rho^{\prime\prime}(T_{u})+1)}\,\,+\sum\limits_{\begin{subarray}{c}u\in
C(v),\\\ u\textrm{ Type 2}\end{subarray}}{\hskip-8.0pt\rho^{\prime}(T_{u})}$

readily follows. On the other hand, if all children of $v$ are of Type 2, then
let $u^{*}$ be a vertex in $C(v)$ such that
$\rho^{\prime\prime}(T_{u^{*}})-\rho^{\prime}(T_{u^{*}})$ is the smallest
possible among all vertices in $C(v)$. Letting $S^{*}$ be an EOP in $T_{v}$,
in which $v$ is the center of the star $R$ containing only $v$ and $u^{*}$, we
infer

$\begin{array}[]{lll}\rho^{c}(T_{v})\geq|S^{*}|&\geq&\sum\limits_{u\in
C(v)\setminus\\{u^{*}\\}}{\hskip-8.0pt\rho^{\prime}(T_{u})+\rho^{\prime\prime}(T_{u^{*}})+1}\\\
\\\ &=&\sum\limits_{u\in
C(v)}{\hskip-8.0pt\rho^{\prime}(T_{u})}+\rho^{\prime\prime}(T_{u^{*}})+1-\rho^{\prime}(T_{u^{*}})\\\
\\\ &=&\sum\limits_{u\in
C(v)}{\hskip-8.0pt\rho^{\prime}(T_{u})}+\min\limits_{u\in
C(v)}\\{\rho^{\prime\prime}(T_{u})+1-\rho^{\prime}(T_{u})\\},\end{array}$

leading to the desired equality. The proof is complete. ∎

######  Lemma 3.3.

For the rooted tree $T$ and $v\in V(T)$,

$\rho^{\ell}(T_{v})=\max\limits_{u\in
C(v)}\Big{\\{}\\!\max\\{\rho^{c}(T_{u}),\rho^{\prime\prime}(T_{u})\\}+1+\hskip-8.0pt\sum\limits_{w\in
C(v)\setminus\\{u\\}}\hskip-10.0pt{\rho^{\prime}(T_{w})}\,\Big{\\}}.$

###### Proof.

Let $S$ be an EOP set of $T_{v}$, which satisfies the conditions from the
definition of $\rho^{\ell}(T_{v})$. That is, $v$ is a leaf of a star $R$ in
$T_{v}[S]$. Therefore, exactly one vertex in $C(v)$ is the center of the star
$R$, and denote it by $u$. Clearly, none of the edges $vw$, where $w\in
C(v)\setminus\\{u\\}$, belongs to $S$. In addition, since $S$ is an EOP set of
$T_{v}$, no vertex $w\in C(v)\setminus\\{u\\}$ is incident with an edge from
$S$. For any $x\in C(v)$, let $S_{x}=S\cap E(T_{x})$. If $w\neq u$, then
$S_{w}$ is an EOP set of $T_{w}$ such that $w\notin V(T_{w}[S_{w}])$.
Therefore, $|S_{w}|\leq\rho^{\prime}(T_{w})$. On the other hand, since $u$ is
the center of the star $R$ in $T_{v}[S]$, there are two possibilities for the
edges from $S_{u}$ depending on the order of $R$. If $R\cong K_{1,1}$, then
none of the vertices in $N[u]\cap V(T_{u})$ can be in $T_{u}[S_{u}]$, and so
$|S_{u}|\leq\rho^{\prime\prime}(T_{u})$. If $|V(R)|\geq 3$, then some of the
edges between $u$ and vertices in $C(u)$ are in $S_{u}$. Hence,
$|S_{u}|\leq\rho^{c}(T_{u})$. Taking into account both possibilities, we
readily infer that
$|S_{u}|\leq\max\\{\rho^{\prime\prime}(T_{u}),\rho^{c}(T_{u})\\}.$ Combining
all findings from above, we get

$|S|=|S_{u}|+1+\hskip-10.0pt\sum\limits_{w\in
C(v)\setminus\\{u\\}}{\hskip-10.0pt|S_{w}|}\leq\max\limits_{u\in
C(v)}\Big{\\{}\\!\max\\{\rho^{c}(T_{u}),\rho^{\prime\prime}(T_{u})\\}+1+\hskip-8.0pt\sum\limits_{w\in
C(v)\setminus\\{u\\}}\hskip-10.0pt{\rho^{\prime}(T_{w})}\,\Big{\\}}.$

On the other hand, the construction described in the previous paragraph leads
to an EOP set $S$ of $T_{v}$ of desired cardinality. In this construction, $v$
is a leaf of a star $R$ in $T_{v}[S]$, one of its children $u$ is the center
of $R$, $S\cap E(T_{u})$ is either a $\rho^{c}(T_{u})$-set or a
$\rho^{\prime\prime}(T_{u})$-set (depending on which of these sets is larger),
and in all other sets $S\cap E(T_{w})$, where $w\in C(v)\setminus\\{u\\}$, we
can take a $\rho^{\prime}(T_{w})$-set. By taking a maximum possible such set
$S$ over all $u\in C(v)$, we infer that the claimed value for $|S|$ is
achieved. ∎

######  Lemma 3.4.

For the rooted tree $T$ and $v\in V(T)$,

$\rho^{\prime}(T_{v})=\sum\limits_{u\in C(v)}{\rho_{e}^{o}(T_{u})}.$

###### Proof.

Let $S$ be an EOP set of $T_{v}$, which satisfies the conditions from the
definition of $\rho^{\prime}(T_{v})$. That is, $v$ is not incident with an
edge from $S$. For any $u\in C(v)$, let $S_{u}=S\cap E(T_{u})$. Note that
$S_{u}$ is an EOP set of $T_{u}$, and so $|S_{u}|\leq\rho_{e}^{o}(T_{u})$.
Thus, $|S|=\sum_{u\in C(v)}{|S_{u}|}\leq\sum_{u\in
C(v)}{\rho_{e}^{o}(T_{u})}$. On the other hand, taking a
$\rho_{e}^{o}(T_{u})$-set $S_{u}$ in $T_{u}$ for each $u\in C(v)$, the union
of all these sets $S_{u}$ yields an EOP set of $T_{v}$ of cardinality
$\sum_{u\in C(v)}{\rho_{e}^{o}(T_{u})}$, which completes the proof of the
lemma. ∎

Input: A tree $T$ on $n$ vertices.

Output: $\rho_{e}^{o}(T)$.

1

2 Fix a root $r\in V(T)$, and let $v_{1},v_{2},\ldots,v_{n-1},v_{n}=r$ be the
vertices of $T$ listed in reverse order with respect to the time they are
visited by a breadth-first traversal of $T$ from $r$;

3for  _$i=1,\ldots,n$_ do

4 Let $C(v_{i})$ be the set of children of $v_{i}$

5

6 if  _$C(v_{i})=\emptyset$_ then

7 $\rho_{e}^{o}(T_{v_{i}})\leftarrow 0$, $\rho^{c}(T_{v_{i}})\leftarrow 0$,
$\rho^{\ell}(T_{v_{i}})\leftarrow 0$, $\rho^{\prime}(T_{v_{i}})\leftarrow 0$,
$\rho^{\prime\prime}(T_{v_{i}})\leftarrow 0$; $v_{i}\leftarrow$ Type 1

8 else

9 $\rho^{\prime\prime}(T_{v_{i}})\leftarrow\sum\limits_{u\in
C(v_{i})}{\rho^{\prime}(T_{u})}$

10 $\rho^{\prime}(T_{v_{i}})\leftarrow\sum\limits_{u\in
C(v_{i})}{\rho_{e}^{o}(T_{u})}$

11 if  _$\rho^{\prime\prime}(T_{v_{i}})+1\geq\rho^{\prime}(T_{v_{i}})$_ then

12 $v_{i}\leftarrow$ Type 1

13 else

14 $v_{i}\leftarrow$ Type 2

15

16 for  _$u\in C(v_{i})$_ do

17
$M_{u}\leftarrow\max\\{\rho^{c}(T_{u}),\rho^{\prime\prime}(T_{u})\\}+1+\hskip-8.0pt\sum\limits_{w\in
C(v_{i})\setminus\\{u\\}}\hskip-10.0pt{\rho^{\prime}(T_{w})}$

18

19 $\rho^{\ell}(T_{v_{i}})\leftarrow\max\limits_{u\in C(v_{i})}{M_{u}}$

20 if  _$\forall u\in C(v_{i})[u={\rm Type\,\,2}]$_ then

21 $D\leftarrow\min\limits_{u\in
C(v_{i})}\\{\rho^{\prime\prime}(T_{u})+1-\rho^{\prime}(T_{u})\\}$

22 $\rho^{c}(T_{v_{i}})\leftarrow\sum\limits_{u\in
C(v_{i})}{\hskip-8.0pt\rho^{\prime}(T_{u})}+D$

23 else

24 $\rho^{c}(T_{v_{i}})\leftarrow\sum\limits_{\begin{subarray}{c}u\in
C(v_{i}),\\\ u=\textrm{ Type
1}\end{subarray}}{\hskip-10.0pt(\rho^{\prime\prime}(T_{u})+1)}\,\,+\sum\limits_{\begin{subarray}{c}u\in
C(v_{i}),\\\ u=\textrm{ Type
2}\end{subarray}}{\hskip-8.0pt\rho^{\prime}(T_{u})}$

25

26
$\rho_{e}^{o}(T_{v_{i}})\leftarrow\max\\{\rho^{c}(T_{v_{i}}),\rho^{\ell}(T_{v_{i}}),\rho^{\prime}(T_{v_{i}})\\}$

27

return _$\rho_{e}^{o}(T_{r})$_

Algorithm 1 EOP number of a tree

######  Lemma 3.5.

For the rooted tree $T$ and $v\in V(T)$,

$\rho^{\prime\prime}(T_{v})=\sum\limits_{u\in C(v)}{\rho^{\prime}(T_{u})}.$

###### Proof.

Let $S$ be an EOP set of $T_{v}$, which satisfies the conditions from the
definition of $\rho^{\prime\prime}(T_{v})$. That is, $v$ is not incident with
an edge from $S$, and also none of the children $u\in C(v)$ is incident with
an edge from $S$. For any $u\in C(v)$, let $S_{u}=S\cap E(T_{u})$. Note that
$S_{u}$ satisfies the conditions from the definition of
$\rho^{\prime}(T_{u})$, and so $|S_{u}|\leq\rho^{\prime}(T_{u})$. We infer
that $|S|=\sum_{u\in C(v)}{|S_{u}|}\leq\sum_{u\in
C(v)}{\rho^{\prime}(T_{u})}$. On the other hand, taking a largest EOP set
$S_{u}$ in $T_{u}$ for each $u\in C(v)$, such that $u$ is not incident with an
edge from $S_{u}$, the union $S^{\prime}$ of all these sets $S_{u}$ yields an
EOP set of $T_{v}$ of cardinality $\sum_{u\in C(v)}{\rho^{\prime}(T_{u})}$.
Clearly, $S^{\prime}$ is an EOP set of $T_{v}$, such that $N[v]\cap
V(T_{v}[S^{\prime}])=\emptyset$, which completes the proof of the lemma. ∎

Based on the above statements we deduce an efficient algorithm for determining
$\rho_{e}^{o}(T)$ for an arbitrary tree $T$ (see Algorithm 1).

As a consequence of Observation 3.1 and Lemmas 3.2, 3.3, 3.4 and 3.5, we
derive that Algorithm 1 correctly computes the EOP number of a tree $T$.

Let us now consider the algorithm’s complexity. (Let $n$ and $m$ stand for the
order and the size of $T$, respectively). The vertex ordering
$v_{1},\ldots,v_{n}$ can be computed in $O(n)$ time using a breadth-first
traversal from $r$. At each leaf (vertex $v_{i}$ with $C(v_{i})=\emptyset$), a
constant number of operations is performed. At each internal vertex $v_{i}$,
$O(|C(v_{i})|)$ operations are performed (assuming, as usual, that adding and
comparing two numbers can be done in $O(1)$ time). This clearly yields that
one can bound the time complexity of the algorithm by $O(m)$, which is
equivalent to $O(n)$. We have thus proved the following result.

######  Theorem 3.6.

There exists a linear-time algorithm for computing the edge open packing
number of a tree.

We note that the results of this section and their proofs imply that Algorithm
1 can be modified so that it also obtains a maximum EOP set of the input tree
$T$. At every vertex $v_{i}$, we can additionally obtain the edges of
$S_{v_{i}}$ according to the corresponding parameter. Notably, in lines 7, 8,
15, 18 or 20, and 21, we can additionally obtain the edges of the
corresponding five copies of $T_{v_{i}}$ by using the constructions from
corresponding lemmas.

##  4 Two bounds and realization results

In this section, we first describe the structure of all graphs with given EOP
number and minimum degree for which the number of edges is as small as
possible. We then study how the EOP number changes under edge removal.

###  4.1 Extremal graphs for the bound $\rho_{e}^{o}(G)\leq|E(G)|/\delta(G)$

Chelladurai et al. [3] showed that the EOP number of a graph $G$ of size $m$
can be bounded from above by $m/\delta(G)$. They also posed the open problem
of characterizing all graphs for which the equality holds in the upper bound.

In this section, we give a complete solution to the above-mentioned problem.
To do so, we define the family $\cal F$ as follows. Let $G$ be a bipartite
graph of minimum degree $k\geq 2$ with partite sets $A\cup C$ and $B$ such
that every vertex in $B$ has $1$ and $k-1$ neighbors in $A$ and $C$,
respectively.

######  Theorem 4.1.

For any graph $G$ of size $m$, $\rho_{e}^{o}(G)=m/\delta(G)$ if and only if
either $G$ is a disjoint union of stars or $G\in\cal F$.

###### Proof.

The equality evidently holds when $G$ is isomorphic to a disjoint union of
stars. So, let $G\in\cal F$. We observe that the subgraph of $G$ induced by
$A\cup B$ is a disjoint union of induced stars. Therefore, $[A,B]$ is an EOP
set in $G$. By the structure of $G$, described in the definition $\cal F$, we
observe that

$\rho_{e}^{o}(G)\geq|[A,B]|=|B|=\dfrac{|B|+(k-1)|B|}{k}=\dfrac{m}{\delta(G)}.$

This results in the equality $\rho_{e}^{o}(G)=m/\delta(G)$.

In order to prove the converse implication, we first give a proof of the upper
bound $\rho_{e}^{o}(G)\leq m/\delta(G)$ for any graph $G$ of size $m$. Let $P$
be a $\rho_{e}^{o}(G)$-set and let $xy$ be an arbitrary edge in $P$. Since $P$
is an EOP set of $G$, it follows that at least one of $x$ and $y$, say $x$, is
adjacent to $\deg(x)-1$ vertices in $V(G)\setminus V(G[P])$. This shows that
every edge in $P$ is adjacent to at least $\delta(G)-1$ edges not in $P$.
Therefore,

$m=|P|+|[V(G[P]),V(G)\setminus V(G[P])]|+|[V(G)\setminus V(G[P]),V(G)\setminus
V(G[P])]|\geq|P|+(\delta(G)-1)|P|.$ (7)

So, $\rho_{e}^{o}(G)=|P|\leq m/\delta(G)$.

Now let $\rho_{e}^{o}(G)=m/\delta(G)$ for a graph $G$, of size $m$ and order
$n$, different from a disjoint union of stars. Therefore, we necessarily have
equality in (7). With this in mind, there is no edge with both endvertices in
$V(G)\setminus V(G[V(P)])$, for otherwise we end up with
$\rho_{e}^{o}(G)<m/\delta(G)$. Note that $G[V(P)]$ is a disjoint union of some
induced stars $S_{1},\ldots,S_{t}$ with centers $a_{1},\ldots,a_{t}$,
respectively. Set $A^{\prime}=\\{a_{1},\ldots,a_{t}\\}$,
$B^{\prime}=\bigcup_{i=1}^{t}(V(S_{i})\setminus\\{a_{i}\\})$ and
$C^{\prime}=V(G)\setminus(A^{\prime}\cup B^{\prime})=V(G)\setminus
V(G[V(P)])$. Notice that $C^{\prime}\neq\emptyset$ because $G$ is different
from a disjoint union of induced stars. Together the equality in (7) and the
fact that $P$ is an EOP set in $G$ imply that every vertex in $B^{\prime}$ is
adjacent to precisely $\delta(G)-1$ vertices in $C^{\prime}$ and to exactly
one vertex in $A^{\prime}$ (in particular, this shows that $\delta(G)\geq 2$).
Moreover, no vertex in $A^{\prime}$ has a neighbor in $A^{\prime}\cup
C^{\prime}$. In particular, the induced subgraph $G[A^{\prime}\cup
C^{\prime}]$ is edgeless. On the other hand, since $P$ is an EOP set in $G$,
there is no edge with endvertices in $B^{\prime}$. The above argument shows
that $G[B^{\prime}\cup C^{\prime}]$ and $G[A^{\prime}\cup B^{\prime}]$ are
bipartite graphs in which every vertex in $B^{\prime}$ is adjacent to
$\delta(G)-1$ vertices in $C^{\prime}$ and to one vertex in $A^{\prime}$. We
now observe that $\delta(G)$, $A^{\prime}$, $B^{\prime}$ and $C^{\prime}$ have
the same roles as $k$, $A$, $B$ and $C$ have in the description of the members
of $\cal F$, respectively. Consequently, $G$ belongs to $\cal F$. ∎

###  4.2 Effect of edge removal

Analysis of the effect of edge removal on the value of $\rho_{e}^{o}$ was
suggested in [3], and here we give a comprehensive response. Note that
characterizations of the graphs with $\rho_{e}^{o}(G)\in\\{1,2\\}$ were also
given in [3]. In fact, it is easy to see that $\rho_{e}^{o}(G)=1$ if and only
if $G\cong K_{n}$ for $n\geq 2$. Moreover, $\rho_{e}^{o}(G)=2$ if and only if
$(i)$ $2\leq\mbox{diam}(G)\leq 4$, $(ii)$ $G$ is claw-free and $(iii)$ for any
two nonadjacent edges $e_{1}=uv$ and $e_{2}=xy$ having no common edge, every
vertex in $V(G)\setminus\\{u,v,x,y\\}$ is adjacent to at least two vertices in
$\\{u,v,x,y\\}$.

It is clear that $\rho_{e}^{o}(K_{n}-e)=2=\rho_{e}^{o}(K_{n})+1$ for each edge
$e$ when $n\geq 3$. So, we consider the graphs $G$ with $\rho_{e}^{o}(G)\geq
2$.

######  Theorem 4.2.

For any graph $G$ of order $n\geq 3$ and $e\in E(G)$, the following statements
hold.

  1. (i)

If $\rho_{e}^{o}(G)=2$, then $1\leq\rho_{e}^{o}(G-e)\leq 3$.

  2. (ii)

If $\rho_{e}^{o}(G)\geq 3$, then $\rho_{e}^{o}(G)-1\leq\rho_{e}^{o}(G-e)\leq
2(\rho_{e}^{o}(G)-1)$.

###### Proof.

First, let us consider the upper bound. Let $B$ be a $\rho_{e}^{o}(G-e)$-set.
Note that the subgraph of $G$ induced by $B$ is a disjoint union of induced
stars $S_{1},\ldots,S_{k}$ with centers $s_{1},\ldots,s_{k}$, respectively (if
$S_{i}$ has only one edge for some $1\leq i\leq k$, then we only consider one
of its endvertices as the center). If $B$ turns out to be an EOP set of $G$,
then $\rho_{e}^{o}(G-e)\leq\rho_{e}^{o}(G)$, which is less than or equal to
$2(\rho_{e}^{o}(G)-1)$. So, we may assume that $B$ is not an EOP set of $G$.
This implies that $e$ joins a vertex $x\in V(S_{i})$ to a vertex $y\in
V(S_{j})$ for some $1\leq i\leq j\leq k$. We deal with the following
possibilities.
(a) Let $x=s_{i}$ and $y$ is a leaf of $S_{j}$ for some $1\leq i<j\leq k$.
Then, $B\setminus\\{ys_{j}\\}$ is an EOP set of $G$ of cardinality
$\rho_{e}^{o}(G-e)-1$. So, $\rho_{e}^{o}(G-e)\leq\rho_{e}^{o}(G)+1$.
(b) Let $x$ be a leaf of $S_{i}$ and $y$ be a leaf of $S_{j}$ for some $1\leq
i\leq j\leq k$ ($i$ may be equal to $j$). Then, $B\setminus\\{xs_{i}\\}$ is an
EOP set of $G$ of cardinality $\rho_{e}^{o}(G-e)-1$. Hence,
$\rho_{e}^{o}(G-e)\leq\rho_{e}^{o}(G)+1$.
(c) Let $x=s_{i}$ and $y=s_{j}$ for some $1\leq i<j\leq k$. We may assume,
without loss of generality, that $|E(S_{i})|\leq|E(S_{j})|$. In such a case,
$B^{\prime}=\big{(}B\setminus E(S_{i})\big{)}\cup\\{e\\}$ is an EOP set in
$G$. Thus, $\rho_{e}^{o}(G)\geq|B^{\prime}|\geq|B|/2+1=\rho_{e}^{o}(G-e)/2+1$.
Summing up, we have proved that
$\rho_{e}^{o}(G-e)\leq\max\\{2\rho_{e}^{o}(G)-2,\rho_{e}^{o}(G)+1\\}$ in each
case, which proves the upper bounds in $(i)$ and $(ii)$.

For the lower bounds, note that if $B$ is a $\rho_{e}^{o}(G)$-set, then
$B\setminus\\{e\\}$ is an EOP set in $G-e$ for each $e\in E(G)$. This leads to
$\rho_{e}^{o}(G)-1\leq\rho_{e}^{o}(G-e)$. ∎

In the next remark we show that all integer values between the lower and upper
bounds in Theorem 4.2 are realizable.

######  Observation 4.3.

For any integers $b\geq 3$ and $a$ with $b-1\leq a\leq 2b-2$, there exists a
connected graph $G$ and $e\in E(G)$ such that $\rho_{e}^{o}(G)=b$ and
$\rho_{e}^{o}(G-e)=a$. In addition, for any $a\in\\{1,2,3\\}$ there exists a
connected graph $G$ and $e\in E(G)$ such that $\rho_{e}^{o}(G)=2$ and
$\rho_{e}^{o}(G-e)=a$.

###### Proof.

Let $b\geq 3$. First, let $b+1\leq a\leq 2b-2$. Let $G$ be obtained from
$K_{1,b+1}$, with leaves $v_{1},\ldots,v_{b+1}$ and central vertex $v$, by
$(i)$ attaching $\lfloor a/2\rfloor$ new vertices to $v_{1}$ as leaves and
also $\lceil a/2\rceil$ new vertices to $v_{2}$ as leaves, and $(ii)$ adding
the edge $v_{1}v_{2}$. It is not difficult to check that $\rho_{e}^{o}(G)=b$
and $\rho_{e}^{o}(G-v_{1}v_{2})=a$. Second, let $a=b$. Consider the graph
$G^{\prime}$ obtained from the above-mentioned graph $G$ by removing the
vertices in $(i)$. We then have
$\rho_{e}^{o}(G^{\prime})=\rho_{e}^{o}(G^{\prime}-vv_{1})=b$. Third, let
$a=b-1$. Let $G^{\prime\prime}$ be obtained from the paths $vv_{i}w_{i}$, for
$1\leq i\leq b$, by adding edges in such a way that the set
$\\{w_{1},w_{2},\ldots,w_{b}\\}$ induces a clique. One can easily check that
$\rho_{e}^{o}(G^{\prime\prime})=b$ and
$\rho_{e}^{o}(G^{\prime\prime}-vv_{b})=b-1$.

Suppose now that $b=2$. Let $G$ be obtained from $K_{n}$, with $n\geq 3$, by
joining a new vertex $v$ to a vertex $u\in V(K_{n})$. It is then clear that
$\rho_{e}^{o}(G)=2=\rho_{e}^{o}(G-uv)+1$. Moreover,
$\rho_{e}^{o}(G)=2=\rho_{e}^{o}(G-xy)-1$ for any edge $xy$ of $K_{n}$ with
$x,y\neq u$. Finally, $\rho_{e}^{o}(G)=2=\rho_{e}^{o}(G-uw)$ in which $u\neq
w\in V(K_{n})$. ∎

## Acknowledgement

B.B. was supported by the Slovenian Research and Innovation Agency (ARIS)
under the grants P1-0297, N1-0285, J1-3002, and J1-4008.

## References

  * [1] K. Cameron, Induced matchings, Discrete Appl. Math. 24 (1989), 97–102.
  * [2] D.M. Cardoso, J.O. Cerdeira, J.P. Cruz and C. Dominic, Injective edge coloring of graphs, Filomat, 33 (2019), 6411–6423.
  * [3] G. Chelladurai, K. Kalimuthu and S. Soundararajan, Edge open packing sets in graphs, RAIRO-Oper. Res. 56 (2022), 3765–3776.
  * [4] K.K. Dabrowski, M. Demange and V.V. Lozin, New results on maximum induced matchings in bipartite graphs and beyond, Theoret. Comput. Sci. 478 (2013), 33–40.
  * [5] F. Foucaud, H. Hocquard and D. Lajou, Complexity and algorithms for injective edge-coloring in graphs, Inform. Process. Lett. 170 (2021), 106121.
  * [6] M.R. Garey and D.S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, W.H. Freeman $\&$ Co., New York, USA, 1979.
  * [7] M.R. Garey, D.S. Johnson and L. Stockmeyer, Some simplified NP-complete graph problems, Theoret. Comput. Sci. 1 (1976), 237–267.
  * [8] V.V. Lozin, On maximum induced matchings in bipartite graphs, Inform. Process. Lett. 81 (2002), 7–11.
  * [9] Z. Miao, Y. Song and G. Yu, Note on injective edge-coloring of graphs, Discrete Appl. Math. 310 (2022), 65–74.
  * [10] L.J. Stockmeyer and V.V. Vazirani, NP-completeness of some generalizations of the maximum matching problem, Inform. Process. Lett. 15 (1982), 14–19.
  * [11] D.B. West, Introduction to Graph Theory (Second Edition), Prentice Hall, USA, 2001.
  * [12] M. Zito, Induced matchings in regular graphs and trees, Graph-theoretic concepts in computer science, 1665 (1999), 89–101.


# The Integer-Magic Spectra of Trees

Alvaro Carboneroa and Dylan Obatab
a,bUniversity of Nevada, Las Vegas
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### 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\mathbb{Z}_{h}-\\{0\\}$ such that the
induced vertex set labeling $\ l^{+}:V(G)\to\mathbb{Z}_{h}\ $ defined by

$l^{+}(v)=\sum_{uv\in E(G)}\ l(uv)$

is a constant map. The integer-magic spectrum of a graph $G$, denoted by
$IM(G)$, is the set of all $h\in\mathbb{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.

MSC: 05C78

##  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)\rightarrow A$ such that

$l^{+}(v)=\sum_{uv\in E(G)}l(uv);$

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 $\mathbb{Z}_{h}$-magic. Similarly, if $l$ is a
$\mathbb{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
[4]; this one is a different generalization of magic graphs and so it does not
relate to the topics covered in this paper.

######  Definition 1.1.

For a graph G, let the integer-magic spectrum of $G$, denoted by $IM(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, 5]. 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 [2].

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.1.

For a tree $T_{2k}$ and an integer $i\geq 0$, let

$D_{i}:=\\{v\in V(T_{2k})\text{ : }d(v,c)=i\\}.$

Trees of diameter $2k+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
$\delta:V(T_{2k+1})\rightarrow\mathbb{N}\cup\\{0\\}$ where
$\delta(v)=\text{min}\\{d(v,c_{1}),d(v,c_{2})\\}$.

######  Definition 2.2.

For a tree $T_{2k+1}$ and an integer $i\geq 0$, let

$D_{i}:=\\{v\in V(T_{2k+1})\text{ : }\delta(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 $2k$ and $2k+1$ diameters, $D_{d}=\emptyset$ if $d>k$;
otherwise, the diameter would be bigger. Furthermore, if the tree has diameter
$2k$, then by definition there must be at least two pendant vertices that are
distance $k$ away from $c$; similarly, for $T_{2k+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 $uv\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 2.3.

For a tree $T_{2k}$ and $u\in V(T_{2k})\setminus\\{c\\}$, let the branch of
$u$, or $B^{u}$, be the induced subgraph of $T_{2k}$ with vertex set:

$\\{v\in V(T_{2k})\text{ : }d(c,u)\leq d(c,v)\text{ and }\forall w\in
P(u,v)\text{ }d(c,u)\leq d(c,w)\\}.$

Furthermore, define $B^{c}=T_{2k}$.

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

######  Definition 2.4.

For a tree of $T_{2k+1}$ and $u\in V(T_{2k+1})\setminus\\{c_{1},c_{2}\\}$, let
the branch of $u$, or $B^{u}$, be the induced subgraph of $T_{2k+1}$ with
vertex set:

$\\{v\in V(T_{2k+1})\text{ : }\delta(u)\leq\delta(v)\text{ and }\forall w\in
P(u,v)\text{ }\delta(u)\leq\delta(w)\\}.$

Furthermore, let $B^{c_{1}}$ be the induced subgraph with vertex set:

$\\{v\in V(T_{2k+1})\text{ : }\delta(c_{1})\leq\delta(v)\text{ and
}c_{2}\not\in 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\not=u$, then we say $v$ extends from $u$. An
important observation to make about these branches is that if $uv\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 2.5.

For a tree $T_{n}$, a vertex $u\in V(T_{n})$ and an integer $m\geq 0$, let

$D^{u}_{m}:=D_{m}\cap V(B^{u}).$

Informally, $D^{u}_{m}$ 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^{u}_{m+1}$
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^{u}_{m+1}=\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 2.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^{u}_{p}$ is nonempty. If
$D^{u}_{p}=\\{w_{1},w_{2},...,w_{\alpha}\\}$, then, for every integer $d$ such
that $d>p$,

$\sum_{i=1}^{\alpha}|D^{w_{i}}_{d}|=|D^{u}_{d}|.$ (1)

###### Proof.

Set $k=\lfloor\frac{n}{2}\rfloor$. 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^{w_{1}}_{d},D^{w_{2}}_{d},...,$ and
$D^{w_{\alpha}}_{d}$ are all pairwise disjoint since their corresponding
branches in $T_{n}$ do not overlap. Thus,

$|\bigcup_{1\leq
i\leq\alpha}D_{d}^{w_{i}}|=\sum_{i=1}^{\alpha}|D^{w_{i}}_{d}|.$

We finish the proof by showing that $\bigcup_{1\leq
i\leq\alpha}D_{d}^{w_{i}}=D^{u}_{d}$. Let $v\in D_{d}^{w_{i}}$ for some $i$
where $1\leq i\leq\alpha$. 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^{u}_{d}$. Then $v\in V(B^{u})$. Since $v$ is further away from the
center than any of the vertices in $D^{u}_{p}$, 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^{w_{i}}_{d}$. ∎

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

######  Corollary 2.1.

For a tree $T_{n}$, let $u$ be a vertex in $D_{m}$ such that $u$ is not a
pendant vertex. If $D^{u}_{m+1}=\\{w_{1},w_{2},...,w_{\alpha}\\}$, then, for
every $d$ such that $d>m+1$,

$\sum_{i=1}^{\alpha}|D^{w_{i}}_{d}|=|D^{u}_{d}|.$

##  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 $-3x$. Thus, the label of the edge
closer to the center needs to be $4x$ so that $l^{+}(v)=-3x+4x=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 3.1.

For a tree $T_{2k}$, define $f:E(T_{2k})\rightarrow\mathbb{Z}$ such that if
$uv\in E(T_{2k})$, $u\in D_{m}$ and $v\in D_{m-1}$, then

$f(uv):=(-1)^{k-m+1}\sum_{i=1}^{k-m+1}(-1)^{i}|D^{u}_{k-i+1}|.$

Furthermore, for a tree $T_{2k+1}$, define
$f:E(T_{2k+1})\rightarrow\mathbb{Z}$ such that if $uv\in
E(T_{2k+1})\setminus\\{c_{1}c_{2}\\}$, $u\in D_{m}$ and $v\in D_{m-1}$, then

$f(uv):=(-1)^{k-m+1}\sum_{i=1}^{k-m+1}(-1)^{i}|D^{u}_{k-i+1}|.$

As for $c_{1}c_{2}$, let

$f(c_{1}c_{2}):=(-1)^{k+1}\sum_{i=1}^{k+1}(-1)^{i}|D^{c_{1}}_{k-i+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 3.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 xf(e)\mod{h}.$

###### Proof.

We first prove the statement for $n=2k$. Define

$\hat{D}_{m}=\\{uv\in E(T_{2k})\text{ : }u\in D_{m}\text{ and }v\in
D_{m-1}\\}$

for $m$ such that $1\leq m\leq k$. This partitions $E(T_{2k})$ into $k$ sets.
We will prove the statement by using the principle of backwards induction on
$m$.

For the base case, let $uv\in\hat{D}_{k}$ where $u\in D_{k}$ and $v\in
D_{k-1}$. Since $u\in D_{k}$, then $uv$ is a pendant edge. By definition,
$l(uv)=x$, and so

$\displaystyle xf(uv)$
$\displaystyle=x(-1)^{k-k+1}\sum_{i=1}^{k-k+1}(-1)^{i}|D^{u}_{k-i+1}|$
$\displaystyle=x|D^{u}_{k}|$ $\displaystyle=x$ $\displaystyle=l(uv)\mod{h}.$

We used the fact that for all $u\in D_{i}$, $|D^{u}_{i}|=1$.

Now assume that the statement is true for all edges in $\hat{D}_{m}$. Let
$uv\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(uv)=x$, and so

$\displaystyle xf(uv)$
$\displaystyle=x(-1)^{k-m+1+1}\sum_{i=1}^{k-m+1+1}(-1)^{i}|D^{u}_{k-i+1}|$
$\displaystyle=x(-1)^{k-m}(-|D^{u}_{k}|+...+(-1)^{k-m+2}|D^{u}_{m-1}|)$
$\displaystyle=x(-1)^{k-m}(0+(-1)^{k-m})$ $\displaystyle=x$
$\displaystyle=l(uv)\mod{h}.$

We used the fact that, since $u$ is a pendant vertex, $|D^{u}_{i}|=0$ for all
$i>m-1$.

Assume then that $u$ is not a pendant vertex. Let
$D^{u}_{m}=\\{w_{1},w_{2},...,w_{\alpha}\\}$. Since $l$ is an $h$-magic
labeling,

$l^{+}(u)=l(uv)+\sum_{i=1}^{\alpha}l(uw_{i})\equiv x\mod{h}.$

But $uw_{i}\in\hat{D}_{m}$ for each $1\leq i\leq\alpha$, so we can apply the
induction hypothesis and obtain

$\displaystyle\sum_{i=1}^{\alpha}l(uw_{i})$
$\displaystyle\equiv\sum_{i=1}^{\alpha}xf(uw_{i})$
$\displaystyle=\sum_{i=1}^{\alpha}x(-1)^{k-m+1}\sum_{j=1}^{k-m+1}(-1)^{j}|D^{w_{i}}_{k-j+1}|$
$\displaystyle=x(-1)^{k-m+1}\sum_{i=1}^{\alpha}\sum_{j=1}^{k-m+1}(-1)^{j}|D^{w_{i}}_{k-j+1}|$
$\displaystyle=x(-1)^{k-m+1}\sum_{j=1}^{k-m+1}(-1)^{j}|D^{u}_{k-j+1}|\mod{h}.$

Note that we used Corollary (2.1) in the last step. In the future, we will use
it without reference. From the above fact it follows that

$\displaystyle l(uv)$ $\displaystyle\equiv x-\sum_{i=1}^{\alpha}l(uw_{i})$
$\displaystyle\equiv x-x(-1)^{k-m+1}\sum_{j=1}^{k-m+1}(-1)^{j}|D^{u}_{k-j+1}|$
$\displaystyle=x(1+(-1)^{k-m+2}\sum_{j=1}^{k-m+1}(-1)^{j}|D^{u}_{k-j+1}|)$
$\displaystyle=x((-1)^{2(k-m+2)}|D^{u}_{m-1}|+(-1)^{k-m+2}\sum_{j=1}^{k-m+1}(-1)^{j}|D^{u}_{k-j+1}|)$
$\displaystyle=x(-1)^{k-m+2}((-1)^{k-m+2}|D^{u}_{m-1}|+\sum_{j=1}^{k-m+1}(-1)^{j}|D^{u}_{k-j+1}|)$
$\displaystyle=x(-1)^{k-m+2}\sum_{j=1}^{k-m+2}(-1)^{j}|D^{u}_{k-j+1}|)$
$\displaystyle=xf(uv)\mod{h}.$

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^{c_{1}}_{1}=\\{w_{1},w_{2},...,w_{\alpha}\\}$. Since $l$ is an
$h$-magic labeling,

$l^{+}(c_{1})=l(c_{1}c_{2})+\sum_{i=1}^{\alpha}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\alpha$, then
$l(c_{1}w_{i})\equiv xf(c_{1}w_{i})\mod{h}$. Thus,

$\displaystyle\sum_{i=1}^{\alpha}l(c_{1}w_{i})$
$\displaystyle\equiv\sum_{i=1}^{\alpha}xf(c_{1}w_{i})$
$\displaystyle=\sum_{i=1}^{\alpha}x(-1)^{k}\sum_{j=1}^{k}(-1)^{j}|D^{w_{i}}_{k-j+1}|$
$\displaystyle=x(-1)^{k}\sum_{j=1}^{k}(-1)^{j}|D^{c_{1}}_{k-j+1}|\mod{h}.$

From this, it follows that

$\displaystyle l(c_{1}c_{2})$ $\displaystyle\equiv
x-\sum_{i=1}^{\alpha}l(c_{1}w_{i})$ $\displaystyle\equiv
x(1+(-1)^{k+1}\sum_{j=1}^{k}(-1)^{j}|D^{c_{1}}_{k-j+1}|)$
$\displaystyle=x((-1)^{2(k+1)}|D^{c_{1}}_{0}|+(-1)^{k+1}\sum_{j=1}^{k}(-1)^{j}|D^{c_{1}}_{k-j+1}|)$
$\displaystyle=x(-1)^{k+1}((-1)^{k+1}|D^{c_{1}}_{0}|+\sum_{j=1}^{k}(-1)^{j}|D^{c_{1}}_{k-j+1}|)$
$\displaystyle=x(-1)^{k+1}\sum_{j=1}^{k+1}(-1)^{j}|D^{c_{1}}_{k-j+1}|$
$\displaystyle=xf(c_{1}c_{2})\mod{h}.$

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 3.1.

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

  1. 1.

For every edge $e\in E(T_{n})$,

$xf(e)\not\equiv 0\mod{h}.$ (2)

  2. 2.

    1. (a)

If $n$ is even, then

$x\sum_{i=1}^{k}(-1)^{k+i}|D_{k-i+1}|\equiv x\mod{h}$ (3)

    2. (b)

If $n$ is odd, then

$x\sum_{i=1}^{k}(-1)^{i}|D^{c_{1}}_{k-i+1}|\equiv
x\sum_{i=1}^{k}(-1)^{i}|D^{c_{2}}_{k-i+1}|\mod{h}.$ (4)

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 $xf(e)\equiv 0\mod{h}$. By Lemma 3.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=2k$ and set
$D_{1}=\\{w_{1},w_{2},...,w_{\alpha}\\}$. By using Lemma 3.1, we get the
result:

$\displaystyle x$ $\displaystyle\equiv$ $\displaystyle l^{+}(c)$
$\displaystyle=$ $\displaystyle\sum_{i=1}^{\alpha}l(cw_{i})$
$\displaystyle\equiv$ $\displaystyle\sum_{i=1}^{\alpha}xf(cw_{i})$
$\displaystyle=$ $\displaystyle
x\sum_{i=1}^{\alpha}(-1)^{k}\sum_{j=1}^{k}(-1)^{j}|D^{w_{i}}_{k-j+1}|$
$\displaystyle=$ $\displaystyle x\sum_{j=1}^{k}(-1)^{k+j}|D_{k-j+1}|\mod{h}.$

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

$\displaystyle x$ $\displaystyle\equiv l^{+}(c_{2})$
$\displaystyle=l(c_{1}c_{2})+\sum_{i=1}^{\alpha}l(c_{2}w_{i})$
$\displaystyle\equiv
x(-1)^{k+1}\sum_{i=1}^{k+1}(-1)^{i}|D^{c_{1}}_{k-i+1}|+\sum_{i=1}^{\alpha}x(-1)^{k}\sum_{j=1}^{k}(-1)^{j}|D^{w_{i}}_{k-j+1}|$
$\displaystyle=x(-1)^{k}(-\sum_{i=1}^{k+1}(-1)^{i}|D^{c_{1}}_{k-i+1}|+\sum_{j=1}^{k}(-1)^{j}|D^{c_{2}}_{k-j+1}|)$
$\displaystyle=x(-1)^{k}(-\sum_{i=1}^{k}(-1)^{i}|D^{c_{1}}_{k-i+1}|+\sum_{j=1}^{k}(-1)^{j}|D^{c_{2}}_{k-j+1}|+(-1)^{k})$
$\displaystyle=x(-1)^{k}(-\sum_{i=1}^{k}(-1)^{i}|D^{c_{1}}_{k-i+1}|+\sum_{j=1}^{k}(-1)^{j}|D^{c_{2}}_{k-j+1}|)+x\mod{h}.$

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=2k$ and that there exists an integer $x$ such that (2) and (3) are
true. Define $l(e)=xf(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,

$\displaystyle l^{+}(u)$ $\displaystyle=l(uv)$ $\displaystyle=xf(uv)$
$\displaystyle=-x(-|D^{u}_{k}|)$ $\displaystyle=x.$

Assume $u\in D_{0}$, i.e. $u=c$. If we let
$D_{1}^{u}=\\{w_{1},w_{2},...,w_{\alpha}\\}$, then,

$\displaystyle l^{+}(u)$ $\displaystyle=\sum_{i=1}^{\alpha}l(uw_{i})$
$\displaystyle=\sum_{i=1}^{\alpha}xf(uw_{i})$
$\displaystyle=x\sum_{i=1}^{\alpha}(-1)^{k}\sum_{j=1}^{k}(-1)^{j}|D^{w_{i}}_{k-j+1}|$
$\displaystyle=x\sum_{j=1}^{k}(-1)^{k+j}|D_{k-j+1}|$ $\displaystyle\equiv
x\mod{h}.$

Finally, assume $u\in D_{m}$ where $0<m<k$. The proof of Lemma 3.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 $uv\in E(T_{2k})$, and
$D^{u}_{m+1}=\\{w_{1},w_{2},...,w_{\alpha}\\}$. We obtain the result from the
following.

$\displaystyle l^{+}(u)$ $\displaystyle=l(uv)+\sum_{i=1}^{\alpha}l(uw_{i})$
$\displaystyle=x(-1)^{k-m+1}\sum_{i=1}^{k-m+1}(-1)^{i}|D^{u}_{k-i+1}|+x\sum_{i=1}^{\alpha}(-1)^{k-m}\sum_{j=1}^{k-m}(-1)^{j}|D^{w_{i}}_{k-j+1}|$
$\displaystyle=x(-1)^{k-m}(-\sum_{i=1}^{k-m+1}(-1)^{i}|D^{u}_{k-i+1}|+\sum_{j=1}^{k-m}(-1)^{j}|D^{u}_{k-j+1}|)$
$\displaystyle=x(-1)^{k-m}(-(-1)^{k-m+1}|D^{u}_{m}|)$ $\displaystyle=x.$

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=2k+1$ and assume
there exists an $x$ such that (2) and (4) hold. As with the even case, define
$l(e)=xf(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^{c_{1}}_{1}=\\{w_{1},w_{2},...,w_{\alpha}\\}$. It follows that

$\displaystyle l^{+}(c_{1})$
$\displaystyle=l(c_{1}c_{2})+\sum_{i=1}^{\alpha}l(c_{1}w_{i})$
$\displaystyle=x(-1)^{k+1}\sum_{i=1}^{k+1}(-1)^{i}|D^{c_{1}}_{k-i+1}|+\sum_{i=1}^{\alpha}x(-1)^{k}\sum_{j=1}^{k}(-1)^{j}|D^{w_{i}}_{k-j+1}|$
$\displaystyle=x(-1)^{k}(-\sum_{i=1}^{k+1}(-1)^{i}|D^{c_{1}}_{k-i+1}|+\sum_{j=1}^{k}(-1)^{j}|D^{c_{1}}_{k-j+1}|)$
$\displaystyle=x(-1)^{k}(-(-1)^{k+1}|D^{c_{1}}_{0}|)$ $\displaystyle=x.$

Similarly, if $D^{c_{2}}_{1}=\\{w_{1},w_{2},...,w_{\alpha}\\}$, then

$\displaystyle l^{+}(c_{2})$
$\displaystyle=l(c_{1}c_{2})+\sum_{i=1}^{\alpha}l(c_{2}w_{i})$
$\displaystyle=x(-1)^{k+1}\sum_{i=1}^{k+1}(-1)^{i}|D^{c_{1}}_{k-i+1}|+\sum_{i=1}^{\alpha}x(-1)^{k}\sum_{j=1}^{k}(-1)^{j}|D^{w_{i}}_{k-j+1}|$
$\displaystyle=x(-1)^{k}(-\sum_{i=1}^{k+1}(-1)^{i}|D^{c_{1}}_{k-i+1}|+\sum_{j=1}^{k}(-1)^{j}|D^{c_{2}}_{k-j+1}|)$
$\displaystyle\equiv
x(-1)^{k}(-\sum_{i=1}^{k+1}(-1)^{i}|D^{c_{1}}_{k-i+1}|+\sum_{j=1}^{k}(-1)^{j}|D^{c_{1}}_{k-j+1}|)$
$\displaystyle=x(-1)^{k}(-(-1)^{k+1}|D^{c_{1}}_{0}|)$ $\displaystyle=x.$

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, 5] 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 3.1 that will shed light on the conditions
stated in the main result.

######  Corollary 3.1.

For any $h$-magic tree of diameter $2k$, 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 $2k+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 4.1.

Given a tree $T_{n}$, let $k=\lfloor\frac{n}{2}\rfloor,$ and let

$C:=\\{m\in\mathbb{Z}\text{ : }m|r\text{ for some }r\in\text{Range}(f)\\}.$

When $n$ is even, set

$\sigma:=\sum_{i=1}^{k+1}(-1)^{k+i}|D_{k-i+1}|,$

and when $n$ is odd, set

$\sigma:=\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 $\sigma$ that are not in $C$,
then

$\displaystyle IM(T_{n})=\left\\{\begin{array}[]{cc}\emptyset&\hskip
14.22636pt\text{if }\sigma\in C;\\\ \mathbb{N}-C&\hskip 14.22636pt\text{if
}\sigma=0;\\\ \bigcup_{d\in D}d\mathbb{N}&\hskip
14.22636pt\text{otherwise.}\\\ \end{array}\right.$

###### Proof.

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

Assume $\sigma\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 $\sigma x\equiv 0\mod{h}$. Since
$\sigma\in C$, there exist an edge $e$ such that $\sigma|f(e)$, and so $\sigma
x|xf(e)$. But then, $xf(e)\equiv 0\mod{h}$, so $l(e)\equiv 0\mod{h}$ by Lemma
3.1, which is a contradiction. We conclude $IM(T_{n})=\emptyset$.

Assume then that $\sigma=0$. Let $h\in\mathbb{N}-C$. We will prove that
$T_{n}$ is $h$-magic by showing that $x=1$ satisfies both properties in
Theorem 3.1. From the definition of $C$, we have that $h\nmid f(e)$ for any
edge $e$. In other words, $f(e)\not\equiv 0\mod{h}$, so property 1 is
satisfied. Furthermore, $\sigma=0$ implies property 2. Thus, $T_{n}$ is
$h$-magic, so $h\in IM(T_{n}).$ For the other direction, assume $h\in
IM(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 $xf(e)\equiv 0\mod{h}$, so $l(e)\equiv 0\mod{h}$ by Lemma 3.1,
which is a contradiction. We conclude $h\nmid f(e)$ for all edges, so
$h\in\mathbb{N}-C$. This proves that $IM(T_{n})=\mathbb{N}-C$.

Finally, assume that $\sigma\not\in C$ and $\sigma\not=0$. We have to prove
that $IM(T_{n})=\bigcup_{d\in D}d\mathbb{N}$. Assume first that $h\in
IM(T_{n})$. Let $l$ be an $h$-magic labeling and $x$ be the label of the
pendant edges. Set $d=gcd(\sigma,h)$. We claim that $d\in D$. By definition,
$d|\sigma$, so we only need to prove that $d\not\in C$. We do so by
contradiction, so assume $d|f(e)$ for some $e\in E(T_{n})$. From $\sigma
x\equiv 0\mod{h}$, we know $h|\sigma x$. But since $d=gcd(\sigma,h)$, then
$h|dx$ 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|xf(e)$, or $xf(e)\equiv 0\mod{h}$,
which is a contradiction with Lemma 3.1. Thus, $d\not\in C$, so $d\in D$. And
since $d|h$, there exists a number $p$ such that $dp=h$, i.e.
$h\in\bigcup_{d\in D}d\mathbb{N}$.

We prove the other direction. Let $h\in\bigcup_{d\in D}d\mathbb{N}$. By
definition, $h$ is a multiple of $d\in D$ so set $h=dq$ where
$q\in\mathbb{N}$. We will demonstrate that $q=\frac{h}{d}$ is a choice of $x$
that satisfies both properties in Theorem 3.1. From the definition of $D$,
$d\not=1$, so $\frac{h}{d}\not\equiv 0\mod{h}$. Since $d\not\in C$, $d\nmid
f(e)$ for all edges $e$, or $(\frac{h}{d})d\nmid\frac{h}{d}f(e)$. We conclude
that $\frac{h}{d}f(e)\not\equiv 0\mod{h}$ for all edges, so property 1 is
satisfied. By definition, $d|\sigma$, so $\frac{\sigma}{d}h\equiv 0\mod{h}$.
Thus, property 2 is satisfied. By Theorem 3.1, $T_{n}$ is $h$-magic, and so
$h\in IM(T_{n})$. In other words, $IM(T_{n})=\bigcup_{d\in D}d\mathbb{N}$, and
the proof is done. ∎

## References

  * [1] G. Chartrand and P. Zhang, A First Course in Graph Theory, Dover Publications, New York (2012).
  * [2] J. Gallian, A Dynamic Survey in Graphs Labeling (twenty-second edition), The Electronic Journal of Combinatorics (2019), 129-132.
  * [3] S-M Lee, E. Salehi, and H. Sun, Integer-Magic Spectra of Trees with Diameter at most Four, Journal of Combinatorial Mathematics and Combinatorial Computing 50 (2004), 3-15.
  * [4] C. Meenakshi, and K.M. Kathiresan, A Generalization of Magic and Antimagic Labelings of Graphs, AKCE International Journal of Graphs and Combinatorics 16 (2019), 125-144.
  * [5] E. Salehi and P. Bennett, Integer-Magic Spectra of Trees of Diameter Five, Journal of Combinatorial Mathematics and Combinatorial Computing 66 (2008), 105-111.