Open Packing in H-free Graphs and Subclasses of Split Graphs

Given a graph G(V, E), a vertex subset S of G is called an open packing in G if no pair of distinct vertices in S have a common neighbour in G. The size of a largest open packing in G is called the open packing number of G and is denoted by \(\rho ^o(G)\) . It is interesting to note that the open packing number is a lower bound for the total domination number in graphs with no isolated vertices [Henning and Slater, 1999]. Given a graph G and a positive integer k, Open Packing problem tests whether G has an open packing of size at least k. It is known that Open Packing is NP-complete on split graphs (i.e., the class of \(\{2K_2,C_4,C_5\}\) -free graphs) [Ramos et al. 2014]. In this work, we complete the study on the complexity of Open Packing on H-free graphs for every graph H on at least three vertices by proving that Open Packing is (i) NP-complete on \(K_{1,3}\) -free graphs and (ii) polynomial-time solvable on \((P_4\cup rK_1)\) -free graphs for every \(r\ge 1\) . Further, we prove that Open Packing is (i) NP-complete on \(K_{1,4}\) -free split graphs and (ii) polynomial-time solvable on \(K_{1,3}\) -free split graphs. We prove a similar dichotomy result on split graphs with degree restrictions on the vertices in the independent set of the clique-independent set partition of the split graph.