【doc】偶图Kn,n／I的（m1，m2，…，mr）-圈分解

【doc】偶图Kn,n／I的（m1，m2，…，mr）-圈分解 偶图Kn,n,I的(m1，m2，…，mr)-圈分 解 第4O卷第u期 2006年11月 上海交通大学 JOURNALOFSHANGHAIJIAOTONGUNIVERSITYVo1.40No.11 NOV.2006 文章编号:1006—2467(2006)11—198303 偶图K,卵\的(1,2,…,m)一 蒲利群,沈灏 (上海交通大学数学系,上海200240) 圈分解 摘要:m(1??r)为偶数且?m一2,是?1,K…为偶图,I为K…的一因子.证明了K…\I=l 可分解为(,.,…,)一圈的充分必要条件为2I(n--1)且为奇数.进一步,K…\可分解为 循环的(,mz,…,m)一圈的充分必要条件为2一一1且为奇数. 关键词:(】,2,…,)一圈;分解;偶图;一因子 中图分类号:O157.2文献标识码:A Even(1,m2,…,m)一CycleDecompositionsofK…\J PULi—qu//.SHENHao (Dept.ofMathematics,ShanghaiJiaotongUniv.,Shanghai200240,China) Abstract:Iet(1?i?r)一2,是?1.K…beacompletebipartitegraphandI beaone—factorofK….ItisprovedthatK\canbedecomposedinto(1,2,…,)cy clesifandonly if2In(n一1)andisodd.Moreover,K…\jcanbecyclicallydecomposedinto(l,z,…,)-cyclesif andonlyif2一一1andisodd. Keywords:(1,m2,…,m)一cycle;decomposition;bipartitegraph;one—factor 定义于点集{,口,…,一),边集{, 一li?Z)的图称为圈,记为C(或(, l,…,m】)).S一{l一{1l,l.一1lli? Z一)称为c的差集合.图G一(,E)的圈系为 一 有序点对(,C),其中C为一圈的集合,E中的 每条边仅含于C中的惟一个圈.如果G可 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示为 m圈系,则称G可一圈分解.如果GK,//为(. C)的自同构群,且存在阶为的7l”?//,则称(V,c) 为循环圈系.如果K可表示为循环m一圈系,则 称G可循环圈分解.(,m.,…,)一圈系为边 不相交的m圈的并(1?i?,.).图G=(V,E)的 (,mz,…,m,)圈系也为一组有序点对(V,C), E中的每一条边恰好属于c中的惟一的一个(, m2,…,m)圈.如果(1,m2,…,m)圈系(V.C) 的每一个一圈都是循环的,则称(V,C)为循环的 (l,D12,…,m)一圈系.如果G可表示为(,l,m2, … ,)一圈系,则称G可(,.…,m)一圈分解. 如果G可表示为循环(,m,…,m)一圈系,则称G 可循环(,m,…,m)一圈分解. Linder等_】]综述了图的圈分解.图KK, 及K的m圈分解可参阅文献[2—4].Ma等跚完 善了Archdeacon等_6]的结论,完全解决了K…一 的一圈分解[.Wu【解决了K的(1,,…, 收稿日期:2005—1卜15 基金项目:国家自然科学基金资助项目(10471093) 作者简介:蒲利群(1966一),女,四川成都人,博士生,研究方向为组合设计与编码理论,E—mail;liqunpu@yahoo.COFII.c” 沈灏(联系人),男,教授,博士生导师,电话(Te1.):021—54743148fE—mail:haoshen@sjtu.edu.Cr1. m ? r e g e n e V t S o p e b 1984上海交通大学第4O卷 )一圈分解.Fu等进一步解决了 (1,2,…,)一分解. K2HJ_1的循环C4一((2).,(2s+b十2)l,(2s一1)., 本文以组合数学中的差加作为工具,给出 K…\J的(,,…,)一圈分解. 1K…\的(1,2,…,m,)一圈分解 K为偶图,其顶点集 V(K…)一{0.,1.,…,(n—1).)U {01,1l,…,(n一1)1) 边集E(K…)={iojli,JEZ).令n为正奇数,D ZH,定义图X(n;D)的点集为 ,,(X(n,D))={0.,1.,…,(n一1)o)U {01,1l,…,(n一1)1) 边集为 E(X(n,D))一{i.(+)1IdED,iEZ) 显然,K…一X(n,Z),其中Z称为K的差集合. 取 C一((il)0,(2)1,…,(i一1).,(i)1) 为图X(n;D)的一个肿圈.则当zEZ时, C+z一((1+z).,(2+z)1,…, (im_1+z).,(i+z)1) 也为图X(n;D)的一个舯圈.记 (C)一{C+zIEZ) 称(C)为由C产生的轨道,而c称为轨道(C) 的初始圈.同样地,可定义(,,…,)一圈的轨 道(C,C,,…,C, ). 引理1n为正奇数,b,S为正整数,则在K…中 存在初始圈C其对应的差集合为 R一{b,b+1,…,b+4s一2,b+4s一1} 且RZH. 证明当s一1时,取 C一(O.,(6+3)1,1(6+1)1) 当s>l时,取 C4一(0o,(4s+b,1)l,1.,(4s+b2)1,…, (S—1)0,(3s+6)l,S0,(3s+b一2)l,(S+1)0, (3s+b3)l,…,(2s一1)0,(2s+b一1)1) 引理2n为正奇数,S为正整数,b为非负整 数,则在K…中存在初始圈c,其对应的差集合 为 (1)R一{b,6+2,6+3,…,6+4+2); (2)R一{b,b+1,…,b+4s,b+4s+2}且R Z. 证明对应(1)中的差集合,当s一1时,取 :(2.,(6+5)I,1o,(6+6)1,0.,(6+2)1) 当>1时,取 (2s+b+3)l,…,(+2)o,(3s+b)1, (s+1)0,(3s+6+2)l,S0,(3s+b+3)1,…, 1.,(4s+b+2)1,00,(2s+b)】) 对应(2)中的差集合,当s—l时,取 C6=(O.,(6+3)l,1.,(6+2)1,2.,(6+6)1) 当s>1时,取 C42一(O.,(4s+6)1,1.,(4s+b一1)l,…, (s,2)0,(3s+b+2)l,(s一1)o,(3s+b)l, S(3s+b—1)1,…,(2s一1).,(2s+6)l, (2s)0,(4s+b+2)1) 2主要结论的证明 定理1假设(1??,.)为正偶数且?i1 — 2(五?1),则K…可分解为(.,2,…, )一圈的充分必要条件为2fn(n一1)且n为正奇 数. 证明因(1.2,…,)圈含?m条边,且i竺l 一 圈(1??,.)中的每一点的度数为偶数,必要性 得证. 以下证明充分性.因2ln(n,1)且n为正奇 数,可得n,1—2kt(?1).将(l,.,…,)圈扩 展为(,!,…,)一圈,其中0+一(1? ?,.,1??,).分3种情况证明. 情况1?三o(rood4),1??rt. 取I{i.iIiEZ},因 K…J—X(n,Z\{0)) 故只需证明Z\{0}可分解成不相交差集S的并, 且每个S满足引理l的条件.取 J一1J1 S一{?+1,?+2,…,’ ,一1i1 JJ, ?m1,?}l?J?i1一1 显然,当l~-n时,snS一j2『且?lsI—n一1,因Jl 此Z\{Ot=USj.根据引理1,即得结论.J一1 情况2?三2(rood4),l??rt. 当rt为偶数时,取,一{i.ifi?乙),此时仅考 虑将Z\{0)划分成不相交差集的并.当1?i?rt/2 时,令 2r22广2 SH一{?+1,?+2,…, 第11期蒲利群,等:偶图K…\,的(,,…,)一圈分解l985 2—l 一 1,?m+1} S.一{?m,?m+2,口=1d】 2ii2i2 ?+3,…,?,1,?m)口l?一1d=l 同情况1,易证乙\{o}一Usj.由引理2,易得结论. 当为奇数时,取 ,一{i.(+1)li?乙} 此时仅考虑将Z\{1}划分成不相交差集的并.当 l??rt/2—1时,令 S1={0,2,3,…,ml} 2l—l2z-1 S.一{?m+1,?+2,…,d=1n1 2i2i ?1,?m+l}n坚l口=1 2i2i2一1 S州一{?m,?m+2,?m+3,…,— 14-1d=1 2计12+l ?.一1,?m}d=L4一l 同情况1,易证Zl\{1}一USJ.由引理2,易得结论. 情况3m?兰o(mod4),1??;m?三2(mod 4),J+1??r.令 *0 m(j厂ID4l==m(jl—1)r+i 1?J1?t,1?i?J l~ntj+jl(广-lJ2 1?J1?t,1?Jz?r A一{mlIni*兰0(mod4),1?i?jt} B一{ml/71i*三2(mod4),jt+1?i?} 参照情况2,将Z.f1\{O}(rt—jt为偶数)或Z\ {1}(--jt为奇数)划分成不相交差集的并.参照情 况1,将Z\划分成不相交差集的并.证毕. 定理2可从定理1直接推出. 定理2假设,(1??r)为正偶数且?m=i=l 2(是?1),则K…一f可分解为循环(m,m,…, m)一圈的充分必要条件为2一”一1且”为正奇数. 以上用差的方法解决了K…\,的(,,…, m)一偶圈系的存在性.如果读者感兴趣还可研究以 下问题: (1)K…U,分解为(,,,,m,…,)圈的问 题; (2)去掉?m一2的条件,K…UI或K…\jil 分解为(,.,…,m)一圈的问题. 参考文献: [1]landerCC,RodgerCA.Decompositionsintocycles. II.Cyclesystems,contemporarydesigntheory[M]. [s.1.]:JohnWiley&SonsInc,1992:325—369. E2-1AlspachB,GavlasH.CycledecompositionsofKand Kr[J.JournalofCombinatorialTheory.SeriesB, 99. 2001,81(1):77— E3]SotteauD.DecompositionsofK…(K:. )intocycles (circuits)oflength2k[J].JournalofCombinatorial Theory.SeriesB.1981,30(1):75—81. [4]SftajnaM.Cycledecompositions.III.Completegraphs andfixedlengthcyclesI-J-].JournalofCombinatorial Designs,2002,10(1):27—78. [5]wusI.Even(卅l,2,…,m)一cyclesystemsofthe completegraph[J].ArsComb,2004,70(1):219— 223. [6]FuHI,WuSL.Cyclicallydecomposingthecomplete graphintocycles[J].DiscreteMath,2004,282(1J3): 167—173. E7]顾宗敏,沈灏.双循环Kirkman三元系的存在性EJ]. 上海交通大学,2005,39(1O):1722一I726. GUZong—min,SHENHao.Constructionofcyclically resolvablecyclicKirkmantriplesystems[J].Journal ofShanghaiJiaotongUniversity,2005,39(10):1722— 1726. [8]沈灏,刘振.可分解Mendelsohni无系的相交数 [J].上海交通大学,2003,37(2):298302. SHENHao,IIUZhen.Intersectionnumbersofre solvableMendelsohntriplesystems[J].Journalof 302. ShanghaiJiaotongUniversity,2003,37(2):298— ? 一 : , + m ? 一