完全图循环分解成2-正则图

Cyclically Decomposing the Complete Graph into the 2-regular Graphs

Alspach提出如下猜想:"设n是奇数并且每个m_1,m_2,…,m_h都是大于等于3而小于等于n的整数.若sum from i=1 to h m_i=n(n-1)/2,则K_n可以分解成圈G_(m_1),G_(m_2),…,G_(m_h)."用记号C(m_1^(n_1)m_2^(n_2)…m_s^(n_s))表示由n_i个m_i长圈,i=1,2,…,s组成的2-正则图.设Γ={C((2m_i)^(n_i)…(2m_s)^(n_s))|i∈[1,s]}.研究了循环(K_v,Γ)-分解的构造方法及其存在性问题,并且证明了Alspach猜想的一些特殊情况.

Alspach posed the conjecture ＂let m1, m2,…, mh be positive integers not less than 3 and n be odd. If ^h∑ i=1 mi=n（n-1）/2Then Kn can be decomposed into h cycles Cm1, Cm2,…, Cmh.＂In this paper, we prove some special cases of the conjecture.The symbolC（m1^n1 m2^ n2…ms^ns）denotes a 2-regular graph consisting of ni cycles of length mi, i=1,2,…,s.Let the class of graphsΓ={C（（2mi）^ni…（2ms）^ns）｜i∈[1,s]}. Some construction methods of the cyclic（Kv,Γ）-decompositions are given, and cyclic（Kv,Γ）-decompositions are established.