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, ₄^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 ₑᵒ (G) |E (G) |/ (G), and provide lower and upper bounds for the edge-deleted subgraph of a graph and establish the corresponding realization result.