The packing number of cubic graphs (Q6602335)

A packing in a graph is a set of vertices that are mutually distant at least 3 apart. Using optimization and linear programming to help analyze the greedy algorithm, the authors improve on a result of \textit{O. Favaron} [Discrete Math. 158, No. 1--3, 287--293 (1996; Zbl 0861.05033)] and show that every connected cubic graph of order \(n\) has a packing of size at least \(\frac{17}{132}n-O(1)\). In fact, they prove that there is a constant \(B >1/8\) such that the packing number of every connected cubic graph \(G\) on \(n\) vertices is more than \(B(n-3)\) and deduce such value \(B=17/132\approx 0.1287\) by the help of linear programming.