λKm,n的Pk-分解就是一个(X,β),其中X是λKm,n的顶点集,β是Km,n的子图族,每个子图(称为区组)均同构于Pk,且Km,n中任一边都恰好出现在β的λ个区组中。Ushio在其综述文献中提出了λKm,n的Pk-分解存在性问题的一个猜想。文章证明了该猜想当k=4,5时成立。
A Pk-decomposition of lKm,n is a pair (X, B) where X is the vertex set of Km,n, and B is a collection of subgraphs of Km,n, called blocks, such that each block is isomorphic to Pk and any two distinct vertices in Km,n are joined in exactly l blocks of B. Ushio proposed a conjecture on the existence of a Pk-decomposition of lKm,n. This paper proves that Ushio conjecture is true when k=4, 5.