View PDF HTML (experimental)

Abstract:Packing problems in graphs are fundamental in combinatorial optimization and arise naturally in applications such as resource allocation, scheduling, and communication networks. A classical example is the \emph{induced matching} problem, where one seeks a set of edges whose endpoints induce a matching. In 2022, Chelladurai et al. introduced the notion of \emph{edge open packing}, which can be viewed as a relaxation of induced matching: instead of forcing the selected edges to induce only isolated edges, edge open packing allows them to induce disjoint stars.
For a graph \(G=(V,E)\), two edges \(e_1,e_2\in E(G)\) are said to have a common edge if there exists an edge \(e\in E(G)\setminus\{e_1,e_2\}\) joining an endpoint of \(e_1\) to an endpoint of \(e_2\). A set \(D\subseteq E(G)\) is an \emph{edge open packing set} if no two edges in \(D\) have a common edge, and the maximum cardinality of such a set is the \emph{edge open packing number} \(\rho_e^o(G)\). The corresponding optimization problem is the \textsc{Maximum Edge Open Packing Problem}.
In this paper, we study the computational complexity of the \textsc{Maximum Edge Open Packing Problem}. Motivated by an open question posed by Brešar and Samadi concerning chordal graphs, we investigate the problem on three subclasses of chordal graphs. We give an \(O(n^2)\)-time algorithm for proper interval graphs, an \(O(n+m)\)-time algorithm for block graphs, where \(n=|V(G)|\) and \(m=|E(G)|\), and an \(O(n^3)\)-time algorithm for split graphs. These results provide partial answers to the open question and contribute to the algorithmic understanding of edge packing parameters in chordal graph classes.

Submission history

From: Kamal Santra [view email]
[v1] Fri, 17 Oct 2025 21:56:17 UTC (69 KB)
[v2] Sun, 9 Nov 2025 21:22:11 UTC (69 KB)
[v3] Wed, 29 Jul 2026 11:46:03 UTC (70 KB)