Maximum Complementary \(P_3\)-Packings of \(K_v\)

Abstract

Motivated by the work of Granville, Moisiadis and Rees, we consider in this paper complementary \(P_3\)-packings of \(K_v\). We prove that a maximum complementary \(P_3\)-packing of \(K_v\) (with \(\lfloor\frac{v}{4} \lfloor \frac{2(v-1)}{3}\rfloor \rfloor P_3s\)) exists for all integers \(v \geq 4\), except for \(v = 9\) and possibly for \(v \in \{24, 27, 30, 33, 36, 39, 42, 57\}\).