Packing Three-Vertex Paths in \(2\)-Connected Cubic Graphs

Abstract

We show that every \(2\)-connected cubic graph of order \(n > 8\) admits a \(P_3\)-packing of at least \(\frac{9n}{11}n\) vertices. The proof is constructive, implying an \(O(M(n))\) time algorithm for constructing such a packing, where \(M(n)\) is the time complexity of the perfect matching problem for \(2\)-connected cubic graphs.