2024/06/11 by M. A. Shalu, Shalu, M. A., V. K. Kirubakaran +1
Computer Science · Engineering · #05C85 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.2406.06982
openalex publication_date 2024/06/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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, ρo(G), of 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., \2K2,C4,C5\-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 (P4∪ rK1)-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 (Pt∪ rK1)-free graph, then ρo(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.