P5-factorization of complete bipartite graphs
P5-factorization of complete bipartite graphs
复制标题
完全二部图的 P5 分解
DOI：
10.1016/j.disc.2006.09.046
复制
发表时间：
2008-05
期刊：
影响因子：
--
通讯作者：
中科院分区：
文献类型：
--
作者：
完全二部图Km的一个pk因子，是Km的一个生成子图，使得每个分量都是长度为k的路径。Km的一个pk分解，是Km的一组边不相交的pk因子，n是Km的边集的一个分区，n。当k为偶数时，完全解决了Km，n的pk分解的谱问题。当k是奇数时，Ushio在1993年提出了一个猜想。然而，到目前为止，我们只知道Ushio猜想对k=3是成立的。本文将证明当k=5时Ushio猜想成立。也就是说，我们将证明Km、nis (1) 3n或2m、(2)3m或2n、(3)m+n≡0 （mod5）和(4)5mn/[4(m+n)]的p5分解存在的充分必要条件是一个整数。
A Pk-factor of complete bipartite graph Km,nis a spanning subgraph of Km,nsuch that every component is a path of length k. A Pk-factorization of Km,nis a set of edge-disjoint Pk-factors of Km,nwhich is a partition of the set of edges of Km,n. When k is an even number, the spectrum problem for a Pk-factorization of Km,nhas been completely solved. When k is an odd number, Ushio in 1993 proposed a conjecture. However, up to now we only know that Ushio Conjecture is true for k=3. In this paper we will show that Ushio Conjecture is true when k=5. That is, we shall prove that a necessary and sufficient condition for the existence of a P5-factorization of Km,nis (1) 3n⩾2m, (2) 3m⩾2n, (3) m+n≡0 (mod5), and (4) 5mn/[4(m+n)] is an integer.