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 K₁, ₃-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 W1-complete on K₁, ₃-free graphs and MAX-OPEN PACKING is hard to approximate within a factor of n^ (1{2-) } for any >0 on K₁, ₃-free graphs unless P=NP. Further, we prove that OPEN PACKING is (a) NP-complete on K₁, ₄-free split graphs and (b) polynomial time solvable on K₁, ₃-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.