Open Packing in Graphs: Bounds and Complexity

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 ρᵒ(G). It would be 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, the decision problem OPEN PACKING tests whether G has an open packing of size at least k. The optimization problem MAX-OPEN PACKING takes a graph G as input and finds the open packing number of G. It is known that OPEN PACKING is NP-complete on split graphs (i.e., the class of \2K₂,C₄,C₅\-free graphs) [Ramos et al., 2014]. In this work, we complete the study on the complexity (P vs NPC) of OPEN PACKING on H-free graphs for every graph H with at least three vertices by proving that OPEN PACKING is (i) NP-complete on K1,3-free graphs and (ii) polynomial time solvable on (P₄∪ rK₁)-free graphs for every r≥ 1. In the course of proving (ii), we show that for every t∈ 2,3,4 and r≥ 1, if G is a (Pₜ∪ rK₁)-free graph, then ρᵒ(G) is bounded above by a linear function of r. Moreover, we show that OPEN PACKING parameterized by solution size is W[1]-complete on K1,3-free graphs and MAX-OPEN PACKING is hard to approximate within a factor of n(1/2-δ) for any δ>0 on K1,3-free graphs unless P=NP. Further, we prove that OPEN PACKING is (a) NP-complete on K1,4-free split graphs and (b) polynomial time solvable on K1,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 graphs.