2025/10/17 by Kamal Santra, Santra, Kamal
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Packing Problems #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.2510.16236
openalex publication_date 2025/10/17 · openalex created_date 2025/10/22 · arxiv created 2026/07/29 · arxiv updated 2026/07/30 · openalex updated_date 2026/07/31
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 induced matching problem, where one seeks a set of edges whose endpoints induce a matching. In 2022, Chelladurai et al. introduced the notion of 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 \(e1,e2∈ E(G)\) are said to have a common edge if there exists an edge \(e∈ E(G)∖\e1,e2\\) joining an endpoint of \(e1\) to an endpoint of \(e2\). A set \(D⊆ E(G)\) is an edge open packing set if no two edges in \(D\) have a common edge, and the maximum cardinality of such a set is the edge open packing number \(ρeo(G)\). The corresponding optimization problem is the Maximum Edge Open Packing Problem. In this paper, we study the computational complexity of the 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(n2)\)-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(n3)\)-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.