Minimum complementary P3-coverings of Kv

Abstract

In [2] Granville, Moisiadis and Rees solved the problem of complementary decomposition of K_v into P₃s (paths of length three). In this paper we generalize their work by considering complementary P₃-coverings of K_v. In particular, we show that a minimum complementary P₃-covering of K_v with ⌈v/4 ⌈2(v-1)/3⌉⌉ P₃s exist for all integers v ≥ 4, except possibly for v ∈ {23, 26, 35, 38, 41, 44, 47}.