Edge open packing: complexity, algorithmic aspects, and bounds

Given a graph G, two edges e₁,e₂∈ E(G) are said to have a common edge e if e joins an endvertex of e₁ to an endvertex of e₂. A subset B⊆ 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, ρₑᵒ(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 ρₑᵒ(G)≤ |E(G)|/δ(G), and provide lower and upper bounds for the edge-deleted subgraph of a graph and establish the corresponding realization result.