阿贝尔群中给定度的凯莱图和Hypohamiltonian图的线性k荫度.pdf 43页

分类号密级公开UDC学号20150713012青海师范大学硕士学位论文阿贝尔群中给定度的凯莱图和Hypohamiltonian图的线性k荫度研究生姓名贾楠导师姓名(职称)冶成福，教授申请学位类别硕士学位学科专业名称应用数学研究方向名称组合数学与图论论文提交日期2018年3月论文答辩日期2018年5月学位授予单位青海师范大学学位授予日期2018年6月答辩委员会主席李学良评阅人专家一，专家二 阿贝尔群中给定度的凯莱图和Hypohamiltonian图的线性k荫度中文摘要线性k-森林是每个分支都是长度不超过k的路.一个图G的线性k-荫度,用lak(G)表示,是指分解G需要的最小的线性k-森林的个数.线性1-森林是由一个匹配诱导出来的.图的线性k-荫度的概念由Habib和Peroche提出,是边着色定义的一个自然推广.用la1(G)来表示一个图G的线性1森林,分支是路长不超过1的路,就等价于图G的边着色数χ′(G).线性k-森林是普通线性荫度的一个细化,la(G)(或者la∞(G))表示每个森林的每个分支都是路长不受限制的.图的线性k-荫度是图的着色理论和分解理论中的重要概念.近年来在国内外得到了广泛的研究.本文研究了阿贝尔群中度为3和4的凯莱图以及阶为13、15、16的Hypohamilto-nian图的线性k-荫度.论文的主要内容分为以下五个部分：第一章介绍论文涉及的一些基本概念和符号以及图的线性k-荫度问题的产生和发展,概述本文得到的主要结果.第二章主要写出了已有的结果,包括路、圈、完全图的线性k-荫度.第三章主要研究关于阿贝尔群上的3-正则的连通的凯莱图的线性k-荫度.分别有完全图K4和立方体Q3,P(2h),M(2h)的线性k-荫度.lak(K4)=2或3,lak(Q3)=2或3,lak(P(2h))=2或3,lak(M(2h))=2或3.第四章主要研究关于阿贝尔群上的4-正则的连通的凯莱图的线性k-荫度.分别有C4C4,H(4,h)和G(α,β)的线性k-荫度.lak(C4C4)=4或3,lak(H(4,h))=4或3或2,lak(G(α,β))=4或3或5.第五章主要研究阶为13、15、16的Hypohamiltonian图的线性k-荫度.lak(H(13))=4或3或2,lak(H(15))=4或3或2,lak(H(16))=3或5.设X是一个有限阿贝尔群,它的运算定义为加法.A⊂X{0}使得:a∈A且−a∈A.这里的0是群X上的单位元素.X上的凯莱图Cay(X,A)是一个简单图,其顶点集为X,边集为E={xy|x−y∈A}.在循环群中一个循环图就是凯莱图.Cay(X,A)是连通的当且仅当A是由X生成的.多年来在代数学图论中凯莱图都是重要的研究对象,许多数学和计算机科学家用凯莱图作为网络交流I 的模型.事实上,在具备理论和实践重要性的网络数目上,包括超立方体,蝴蝶图,立方-连通圈,星图和它们的推广,都是凯莱图.若图G不是哈密顿图,且对于v∈V(G),G−v是哈密顿图,则称G为Hypohamiltonian图.关关关键键键词词词:线线线性性性k-森森森林林林,线线线性性性k-荫荫荫度度度,凯凯凯莱莱莱图图图,Hypohamiltonian图图图.II Lineark-arboricityofCaylaygraphsonAbeliangroupswithgivendegreeandHypohamiltonianGraphsAbstractAlineark-forestisaforestwhosecomponentsarepathsoflengthatmostk.Thelineark-arboricityofagraphG,denotedbylak(G),istheleastnumberoflineark-forestsneededtodecomposeG.Clearly,alinear1-forestisinducedbyamatching.Thenotionoflineark-arboricityofagraphwasfirstintroducedbyHabibandPeroche,whichisanaturalgeneralizationofedge-coloring.la(G)isthechromaticindexχ′(G)1ofagraphG.Moreover,thelineark-arboricitylak(G)isalsoarefinementoftheordinarylineararboricity.la(G)(orla∞(G))whichisthecasewheneverycomponentofeachforestisapathwithnolengthconstraint.Thelineark-arboricityofagraphisanimportantconceptinthecoloringtheoryanddecompositiontheory.InthispaperwestudythisinvariantforCayleygraphswithdegree3,4onAbeliangroupsandtheorder13,15,16ofHypohamiltoniangraphs.Themaincontentsofthispaperaredividedintofiveparts:Thefirstchaptermainlyintroducestheapplicationbackground,maincontentsandprogressofthelineark-arboricitystudyongraphsandthebasicconceptsandtermsofgraphtheory.Thesecondchaptermainlywritestheexistedresultsaboutthelineark-arboricityofPn,KnandCn.Thethirdchaptermainlystudiesthelineark-arboricityofCayleygraphswith3-regularonAbeliangroups.Therearelineark-arboricityofcompletegraphK4,cubicQ3,P(2h)andM(2h).lak(K4)=2or3,lak(Q3)=2or3,lak(P(2h))=2or3,lak(M(2h))=2or3.Theforthchaptermainlystudiesthelineark-arboricityofCayleygraphswith4-regularonAbeliangroups.Therearelineark-arboricityofC4C4,H(4,h)andIII G(α,β).lak(C4C4)=4or3,lak(H(4,h))=4,3or2,lak(G(α,β))=4,3or5.Thefifthchaptermainlystudiesthelineark-arboricityoforder13,15,16ofHy-pohamiltoniangraphs.lak(H(13))=4,3or2,lak(H(15))=4,3or2,lak(H(13))=3or5.LetXbeafiniteAbeliangroup,anditsoperationdenotedadditively.AsubsetofX{0}suchthata∈Aimplies−a∈A,where0istheidentityelementofX.TheCayleygraphCay(X,A)isdefinedtohavevertexsetXsuchthatthereisanedgebetweenxandyifandonlyifx−y∈A.AcirculantgraphisaCayleygraphsonacyclicgroup.ObservethatCay(X,A)isconnectedifandonlyifAisagenerat-ingsetofX.Cayleygraphshavebeenimportantobjectsofstudyinalgebraicgraphtheoryovermanyyears.Infact,manymathematiciansandcomputerscientistsrec-ommendCayleygraphsasmodelsforinterconnectionnetworksbecausetheyexhibitmanypropertiesthatensurehighperformance.Infact,anumberofnetworksofboththeoreticalandpracticalimportance,includinghypercubes,butterflies,cube-connectedcycles,stargraphsandtheirgeneralizations,areCayleygraphs.AgraphGissaidtobeHypohamiltonianifitisnothamiltonianbutforeachv∈V(G)thevertexdeletedsubgraphG−vishamiltonian.Keywords:lineark-forest,lineark-arboricity,Cayleygraphs,Hypohamiltoniangraphs.IV 目录中文摘要........................................................I英文摘要........................................................III第一章绪论....................................................1§1.1引言..................................................1§1.2基本概念及术语........................................2§1.3本论文的结构..........................................3第二章Pn,Kn和Cn的线性k-荫度...................................4第三章阿贝尔群上3-正则连通凯莱图的线性k-荫度...................................................6§3.1K4和Q3的线性k-荫度...................................6§3.2P(2h)的线性k-荫度.....................................8§3.3M(2h)的线性k-荫度....................................10第四章阿贝尔群上4-正则连通的凯莱图的线性k-荫度.................12§4.1图C4C4的线性k-荫度..................................14§4.2图H(4,h)的线性k-荫度..................................15§4.3图G(α,β)的线性k-荫度..................................16第五章Hypohamiltonian图的线性k-荫度.............................21§5.1阶为13的Hypohamiltonian图的线性k-荫度..................21§5.2阶为15的Hypohamiltonian图的线性k-荫度..................23§5.3阶为16的Hypohamiltonian图的线性k-荫度..................24第六章总结与展望..............................................29参考文献........................................................30致谢............................................................34 个人简介........................................................35VI 阿贝尔群中给定度的凯莱图和Hypohamiltonian图的线性k荫度第一章绪论§1.1引言在这篇文章中的所有图都是无向的,有限的,简单的.关于图论的概念和术语,我们参考文献[46].对于一个图G,用V(G),E(G),e(G),δ(G)以及∆(G)分别表示图G的顶点集,边集,边的个数,最小度和最大度.N是一个自然数集,[a,b]是一个集合{n∈N|a≤n≤b}.一个图的分解就是将其边集分解形成一些子图,使得每条边仅在一个子图中出现.如果一个图G有一个分解G1,G2,···,Gl,那么我们说G1,G2,···,Gl分解G或者G能被分解为G1,G2,···,Gl.进一步来说,线性k-森林就是一个森林,分支是路长不超过k的路.一个图G的线性k-荫度,用lak(G)表示,是指分解图G需要的最小的线性k-森林的个数.图的线性k-荫度的概念由Habib和Peroche[54]提出,是一个广义的边着色.用la1(G)来表示一个图G的线性1森林,分支是路长不超过1的路,就等价于图G的边着色数χ′(G).另外线性k-森林是普通线性荫度的一个细化,la(G)(或者la∞(G))表示每个森林的每个分支都是路长不受限制的.线性k-荫度的概念早期是由Harary[55]介绍的.有关线性k-荫度更多的细节,我们参考[42,43,44,47,48,49].设X是一个有限阿贝尔群,A⊂X满足:a∈A当且仅当−a∈A.X上的凯莱图Cay(X,A)是一个简单图,其顶点集为X,边集为E={xy|x−y∈A}.在循环群中一个循环图就是凯莱图.凯莱图Cay(X,A)是连通的当且仅当A是由X生成的.凯莱图是一类高对称正则图,被广泛认为是一类理想的互连网络拓扑结构.多年来在代数学图论中凯莱图是重要的研究对象,参考文献[7,10].事实上,许多数学和计算机科学家用凯莱图作为网络交流的模型.参考文献[24,40].事实上,在具备理论和实践重要性的网络数目上,包括超立方体,蝴蝶图,立方-连通圈,星图和它们的推广,都是凯莱图.对于关于凯莱图在交叉网络中作为模型的结果,我们参考文献[24,28].根据凯莱图在网络设计和网络标志性中的重要性,这篇学位论文的目的是研究凯莱图的线性k-荫度.一个图G被称作Hypohamiltonian如果它不是哈密顿的,但是对于每一个v∈V(G)中的顶点删除子图G−v是哈密顿的.学位论文也研究了阶为13,15,16的Hypohamiltonian图的线性k-荫度.1 青海师范大学硕士学位论文§1.2基本概念及术语本文中所考虑的图均为有限无向的简单图.设G=(V(G),E(G))表示有限无向的简单图.对于一个图G,用V(G),E(G),e(G),δ(G)和∆(G)定义图G顶点集,边集,边的个数,最小度和最大度.N是一个自然数集,[a,b]是一个集合{n∈N|a≤n≤b}.一个图的分解就是将其边集分解形成一些子图,使得每条边仅在一个子图中出现.如果一个图G有一个分解G1,G2,···,Gl,那么我们说G1,G2,···,Gl分解G或者G能被分解为G1,G2,···,Gl.用⌈a⌉表示a取上整.让N是一个自然数集,[a,b]是一个集合{n∈N|a≤n≤b}.一个图的分解就是将其边集分解形成一些子图,使得每条边仅在一个子图中出现.如果一个图G有分解G1,G2,···,Gl,那么我们说G1,G2,···,Gl分解G或者G能被分解G1,G2,···,Gl.用Pn,Kn和Cn分别表示顶点个数为n的路,完全图和圈.进一步,线性k-森林就是一个森林,分支是路长不超过k的路.一个图G的线性k-荫度,lak(G)是指分解G需要的最小的线性k-森林的个数.将X定义为一个有限群,它的运算定义为加法.设X是一个有限阿贝尔群,A⊂X满足:a∈A当且仅当−a∈A.X上的凯莱图Cay(X,A)是一个简单图,其顶点集为X,边集为E={xy|x−y∈A}.在循环群中一个循环图就是凯莱图.Cay(X,A)是连通的当且仅当A是由X生成的.多年来在代数学图论中凯莱图是重要的研究对象,参考文献[7,10].许多数学和计算机科学家用凯莱图作为网络交流的模型,参考文献[24,40].在具备理论和实践重要性的基础上,包括超立方体,蝴蝶图,立方-连通圈,星图和它们的推广,都是凯莱图.对于关于凯莱图在交叉网络中作为模型的结果,我们参考文献[24,28].两个图G和H作卡氏积,用GH表示,GH的顶点集是V(G)×V(H),两个顶点(u,v)和(u′,v′)是相邻的当且仅当u=u′且(v,v′)∈E(H),或者v=v′且(u,u′)∈E(G).考虑一个度为4的凯莱图Cay(X,A),其中A={a,b}.由于在[9]中,我们称连接x和x+a的一条边(或者,x和x+b)为a-边(或者,为b-边).由a-边(或者,由b-边)诱导出来的Cay(X,A)的子图是不相交的圈的集合叫做a-圈集(或者b-圈集),每一个的长度为ka(或者,kb)阶为a(或者,阶为b).在Cay(X,A)中令α是a-圈集的数目和β是b-圈集的数目.那么αka=βkb=n.作者在文献[9]中介绍一类简单图,表示为G(α,β)有下面的性质:(i)存在三个正整数α,t,c满足α≥1,t≥3,0≤c={0,b,c,b+c}和X1=X/J={0,b,···,(h−1)b}.令C′=0,b,···,(h−1)b,0和C′′=0,b,b+c,c,0.显然,C′和C′′是Cay(X,A)的两个圈.它在文献[32]中,要么在Cay(X,A)∼=C′C′′或者Cay(X,A)∼=C′C′′或者Cay(X,A)如图2(c)中显示.2它也在文献[32]的类型(c)中显示每一个图同构于C4C4.令G∗是从卡式积图CP通过删除{(u,v)(u,v)|h+1≤i≤2h}中的4h2h2i1i2边而得到的图.其中V(C2h)={u1,u2,...,u2h}和V(P2)={v1,v2}.引引引理理理4.3.如果k≥3,那么la(G∗)=2.k4h13 青海师范大学硕士学位论文证明:如果4≤k≤4h−1,或者k=3和h是偶数,那么从观察2.1和命题3.3可得la(G∗)≤la(CP)=la(P(4h))=2.假设k=3和h是奇数.因为G∗包k4hk2h2k4h含一个圈,然后如下从观察2.2使得la(G∗)≥2.足以证明la(G∗)≤2.那么森34h34h林F1由边集{(u2h,v1)(u1,v1),(uh+1,v1)(uh,v1),(u2h,v2)(u1,v2),(uh,v2)(uh+1,v2)}{(u1,v1)(u1,v2),(uh−1,v1)(uh−1,v2),(uh,v1)(uh,v2)}{}{}h−1h−3(u2i−1,v1)(u2i−1,v2)2≤i≤∪(u2i,v1)(u2i+1,v1)1≤i≤22{}{}h−3h+3∪(u2i,v2)(u2i+1,v2)1≤i≤∪(u2i,v1)(u2i+1,v1)≤i≤h−122{}h+3∪(u2i,v2)(u2i+1,v2)≤i≤h−1,2诱导出来,森林F由边集E(G∗)E(F)诱导出来,在G∗中形成两个线性k-森24h14h林.因此la(G∗)≤2.所以有la(G∗)=2.34h34h§4.1图C4C4的线性k-荫度对于图C4C4,我们有下面的结论.命命命题题题4.1.设k是一个正整数.那么{lak(C4C4)=3,如果3≤k≤15;lak(C4C4)=4,如果k=1,2.通过以下三个引理来证明上面这个命题.引引引理理理4.4.对于图C4C4,la1(C4C4)=4.证明:从引理2.3可得,la1(C4C4)≥∆(C4C4)=4.由引理2.5和2.7,得出la1(C4C4)≤la1(C4)+la1(C4)=2+2=4.所以有la1(C4C4)=4.引引引理理理4.5.对于图C4C4,la2(C4C4)=4.证明:从引理2.2和4.4可得,3≤la2(C4C4)≤la1(C4C4)=4.断言la2(C4C4)=4.假设la2(C4C4)=3.那么C4C4能被分解为三个线性2-森林,记作F1,F2,F3.14 阿贝尔群中给定度的凯莱图和Hypohamiltonian图的线性k荫度因为每一个线性3-森林包含最多2⌊14⌋=10条边在CC中,也就意味着有三344个线性3-森林包含最多30条边在M(2h)中,这与|E(C4C4)|=32相矛盾.因此,la2(C4C4)=4.引引引理理理4.6.对于3≤k≤15,lak(C4C4)=3.⌈⌉δ(C4C4)+1证明:由引理2.2,可得lak(C4C4)≥2=3.注意到E(C4C4)=E(4P)∪E(G∗).由引理4.3,可得la(CC)≤1+la(G∗)=3,因此la(CC)=416k44k16k443.§4.2图H(4,h)的线性k-荫度设C4=v1v2v3v4v1是一个阶为4的圈和Ph=u1u2...uh是一条阶为h的路.那么H(4,h)是从笛卡尔积PhC4通过增加四条边(u1,v1)(uh,v2),(u1,v2)(uh,v1),(u1,v3)(uh,v4),(u1,v4)(uh,v3)得到的图,如图2(c)所示.对于每一个i(1≤i≤h),令Ci是由顶点集{(u,v)|1≤j≤4}诱导出来的圈.对于每一个j(1≤j≤4),ijPj是由顶点集{(u,v)|1≤i≤h}诱导出来的路.ij对于H(4,h),有下面的结论.定定定理理理4.1.令h,k是满足条件h≥3和1≤k≤4h−1的两个正整数.那么2,如果3≤k≤4h−1;3或者4,如果k=2和h≡0(mod3);lak(H(4,h))=4,如果k=1,或者k=2和h̸=0(mod3).通过以下三个引理和一个推论给出上面这个定理的证明.引引引理理理4.7.对于图H(4,h),la1(H(4,h))=4.证明:令F1由边集{(ui,v1)(ui,v2)|1≤i≤h}∪{(ui,v3)(ui,v4)|1≤i≤h},诱导出来F2由边集{(ui,v2)(ui,v3)|1≤i≤h}∪{(ui,v1)(ui,v4)|1≤i≤h}.15 青海师范大学硕士学位论文诱导出来.注意到H(4,h)(E(F1)∪E(F2))是不相交的两个圈的集合C2h,那就是说,H(4,h)(E(F1)∪E(F2))=C2h∪C2h.显然,C2h∪C2h可以分解为两个边不相交的匹配F3,F4,每一个匹配都是线性1-森林.因为F1,F2,F3,F4是在H(4,h)中的四个线性1-森林,由此可得la1(H(4,h))≤4.从引理2.3,可得la1(H(4,h))≥∆(H(4,h))≥4,因此la1(H(4,h))=4.引引引理理理4.8.如果h̸=0(mod3),那么la2(H(4,h))=4.证明:由引理2.1,2.2和4.7,可得3≤la2(H(4,h))≤la1(H(4,h))=4.要证明la2(H(4,h))≥4.假设有相反的情况,la2(H(4,h))=3.那么H(4,h)能被分解成三个线性2-森林,记为F1,F2,F3.因为每一个线性3-森林包含H(4,h)中最多⌊4h×2⌋条边,也就是说三个线性3-森林包含最多3⌊4h×2⌋条边在M(2h)中,这33与|E(H(4,h))|=8h相矛盾,因为h̸=0(mod3).因此,有la2(H(4,h))=4.下面的推论直接从引理2.1,2.2和4.7可得.推推推论论论4.1.如果h≡0(mod3),则有la2(H(4,h))=3或者la2(H(4,h))=4.引引引理理理4.9.对于3≤k≤4h−1,lak(H(4,h))=3.⌈⌉δ(H(4,h))+1证明:从引理2.2可得,lak(H(4,h))≥2=3.下面证明lak(H(4,h))≤3.假设F1是线性3-森林由∪hi(E(C){(ui,v2)(ui,v3)|1≤i≤h}).i=1中的边诱导出来.注意到H(4,h)E(F)=G∗是从笛卡尔积CP=P(2h)中14h2h2通过删掉边{(ui,v2)(ui,v3)|1≤i≤h}所得到的.由3≤k≤4h−1和引理4.3可得la(H(4,h)E(F))=la(G∗)=2,因此la(H(4,h))≤la(G∗)+1=3.k1k4hkk4h§4.3图G(α,β)的线性k-荫度令Ct=v1v2...vtv1阶为t的圈,Ph=u1u2...uh是阶为h的路.那么G(α,β)是由笛卡尔积PhCt通过增加t条边在Ei={(uα,vi)(u1,vi+r)|1≤r≤t}中得到的,这里1≤i≤t.对于每一个i(1≤i≤α),设Ci由顶点集{(u,v)|1≤j≤ijt}诱导出来的圈.对于每一个j(1≤j≤t),Pj由顶点集{(u,v)|1≤i≤α}诱导ij出来的圈;见图2(a).16 阿贝尔群中给定度的凯莱图和Hypohamiltonian图的线性k荫度对于G∈G(α,β),有下面的结论.定定定理理理4.2.设α,t是满足条件1≤α≤αt−1和3≤t≤αt−1的两个正整数.设G∈G(α,β).(1)如果α≥2,那么5,如果α,t是奇数;4,如果α,t是偶数;4或者5如果α,t奇偶性不同;3,或者α≥5,α−1≤k≤αt−1,lak(G)=t≥5,t−1≤k≤αt−1,3或者4或者5,如果α=3或者α=4,或者t=3或者t=4,或者α≥5和2≤k≤α−2,或者t≥5和2≤k≤t−2.(2)如果α=1,那么3,如果⌈n/2⌉≤k≤n−1;3或者4或者5,如果2≤k≤⌈n/2⌉−1;4,如果k=1和n是偶数,la(G)=ck或者n是奇数和n,c是偶数;cn5,如果是奇数和n,c是奇数;c4或者5,如果n是奇数和n是偶数和c是奇数.c通过以下6个引理和1个推论证明上面这个定理.引引引理理理4.10.设G∈G(α,β),这里α≥2.如果α,t都是偶数,那么la1(G)=4.∪αi证明:如果G=CαCt,那么由边集i=1E(C)诱导出来的子图是在G中不相交的集合C1∪C2∪...∪Cα的并.因为t是偶数,接着有C1∪C2∪...∪Cα∪αi能被分解为两个线性1-森林,记作F1,F2.注意到G(i=1E(C))是不相交集合C′∪C′∪...∪C′的并,这里C′是由顶点集V(Pi)(1≤i≤t)诱导出来的圈.那12ti∪αi′′′′么G(i=1E(C))能被分解成两个线性1-森林,记作F1,F2.因为F1,F2,F1,F2是四个1-森林,接着有la1(G)≤4.从引理2.3,有la1(G)≥∆(G)≥4,因此la1(G)=4.17 青海师范大学硕士学位论文∪αi如果G̸=CαCt,那么由边集i=1E(C)所诱导出来的子图,是在G中不相交的C1∪C2∪...∪Cα集合的并,能被分解为两个线性1-森林,记作F,F.注12∪αi意到G(i=1E(C))是一个圈Cαt阶为αt.因为α,t都是偶数,接着有Cαt能被分解为两个线性1-森林,记作F′,F′.因为F,F,F′,F′是四个线性1-森林,接着121212有la1(G)≤4.由引理2.3,可得la1(G)≥∆(G)≥4.因此la1(G)=4.引引引理理理4.11.设G∈G(α,β),这里α≥2.如果α,t都是奇数,那么la1(G)=5.证明:由引理2.1和2.3可得,4≤la1(G)≤5.只需证明la2(G)≥5.假设相反的情况,使得la2(G)=4.那么G能被分解成四个线性1-森林,记作F1,F2,F3,F4.因为α,t都是奇数,每一个线性1-森林包含最多G中(αt−1)条边,因此四个线性1-森2林包含G中最多(4·αt−1)条边,这与|E(G)|=2αt相矛盾.所以有la(G)=5.21下面的推论可以直接从引理2.1和2.3得出.推推推论论论4.2.设G∈G(α,β),这里α≥2.如果α,t有不同的奇偶性,那么la1(G)=4或者la1(G)=5.引引引理理理4.12.设G∈G(α,β).如果α≥5和α−1≤k≤αt−1,那么lak(G)=3.⌈⌉δ(G)+1证明:从引理2.2可得,lak(G)≥2=3.还需证明lak(G)≤3.令H=∪αiG[(i=1E(C))∪{(u1,vj)(u2,vj)|1≤j≤t}].因为α−1≤k≤αt−1,显然有H=tP.接着由H是一个线性k-森林得到GE(H)=P(2t)∪C3∪C4∪α−1...∪Cα.因为α≥5,所以有k≥α−1≥4.因此,根据命题3.3可得,GE(H)能被分解为两个线性k-森林.通过对称性,有以下的结论.引引引理理理4.13.设G∈G(α,β).如果t≥5和t−1≤k≤αt−1,那么lak(G)=3.下面的推论是直接的.推推推论论论4.3.设G∈G(α,β),这里α≥2.如果k满足以下条件之一时,那么3≤la1(G)≤5.(1)α=3或者α=4;(2)t=3或者t=4;18 阿贝尔群中给定度的凯莱图和Hypohamiltonian图的线性k荫度(3)2≤k≤α−2和α≥5;(4)2≤k≤t−2和t≥5.从现在起,考虑α=1的情况.引引引理理理4.14.令G∈G(α,β)有|V(G)|=n,这里α=1.(1)如果n是偶数,或者n是奇数和n,c都是偶数,那么la(G)=4.cc1(2)如果n是奇数和n,c都是奇数,那么la(G)=5.c1(3)如果n是奇数,n是偶数,和c是奇数,那么la(G)=4或者la(G)=5.c11证明:(1)因为n是偶数,接着有n,c都是偶数.因为n是偶数,接着有圈uu...uc12nu能被分解为两个线性1-森林,记作F,F.对于所有的阶为n的圈,因为n112cc是偶数,因此它们中每一个能被分解为两个线性1-森林,记作F3,F4.所以,有la1(G)≤4.从引理2.3,可得la1(G)=4.(2)由引理2.1和2.3,可得la1(G)=4或者la1(G)=5.要证明la1(G)=5.假设有相反的情况,使得la1(G)=4.那么G能被分解为四个线性2-森林,记作F,F,F,F.因为每一个线性1-森林包含G中最多(n−1)条边,因此四个线12342性1-森林最多包含G中(4·n−1)条边,因为n是奇数,所以这与|E(G)|=2n相矛盾.2因此,有la1(G)=5.(3)由引理2.1和2.3,可得la1(G)=4或者la1(G)=5.引引引理理理4.15.设G∈G(α,β)有|V(G)|=n和α=1.如果⌈n⌉≤k≤n,那么la(G)=2k3.证明:设Cn=u1u2...unu1阶为n的圈在G中.注意到G包含圈Cn和一些阶为n的圈.现在给G中一个边着色c颜色为{1,2,3},显示出子图F边集诱导出来ci的色数i(1≤i≤3)是一个线性k-森林.令c(uiui+1)=1如果1≤i≤⌈n/2⌉−1,和c(uiui+1)=2如果⌈n/2⌉≤i≤n.对于在G中的一条边uiui+c,如果c(urur+1)=1对于每一个i≤r≤i+c−1,然后我们用颜色2着边uiui+c;如果c(urur+1)=2对于每一个i≤r≤i+c−1,那么我们用颜色1着边uiui+c.如果c(upup+1)=1但是c(uquq+1)=2对于一些p,q(i≤p,q≤i+c−1),然后我们给了边uiui+c着颜色3.可以很容易的检查G中边着色c,每一个子图Fi其中i(1≤i≤3)是一个19 青海师范大学硕士学位论文⌈⌉δ(G)+1线性k-森林.因此,有lak(G)≤3.由引理2.2,可得lak(G)≥2=3.所以,有lak(G)=3.下面这个推论是显然的.推推推论论论4.4.设G∈G(α,β)有|V(G)|=n和α=1.如果2≤k≤⌈n⌉−1,那2么3≤lak(G)≤5.20 阿贝尔群中给定度的凯莱图和Hypohamiltonian图的线性k荫度第五章Hypohamiltonian图的线性k-荫度我们在这一章研究小顶点Hypohamiltonian图的线性k-荫度.用H(13),H(15),H(16)分别表示阶为13,15,16的图的线性k-荫度.§5.1阶为13的Hypohamiltonian图的线性k-荫度现在研究线性Hypohamiltonian图H(13)的线性k-荫度.命命命题题题5.1.设k是一个正整数.对于Hypohamiltonian图H(13),lak(H(13))=4,如果k=1;lak(H(13))=3,如果2≤k≤5;lak(H(13))=2,如果6≤k≤12.证明:我们区分了以下三个情形来说明这个命题.情情情形形形1:k=1.由引理2.3,可以得到la1(H(13))≥∆(H(13))=4.只需证明la1(H(13))≤4.假设森林F1由边集{u1u2,u3u4,u5u6,u7u8,u9u11,u10u12}诱导出来,森林F2由边集{u1u8,u2u3,u4u5,u6u7,u9u12,u11u13}诱导出来,森林F3由边集{u1u9,u2u6,u3u11,u4u8,u7u12,u10u13}诱导出来,森林F4由边集{u2u10,u5u9,u8u13}诱导出来.形成4个线性1-森林.这意味着la1(H(13))≤4,因此la1(H(13))=4.情情情形形形2:2≤k≤5.⌈⌉⌈⌉δ(H(13))+13+1如果k=2,然后由引理2.2可得la2(H(13))≥==222.那么森林F1由边集{u1u2,u1u8,u3u11,u4u5,u5u6,u7u12,u9u11,u10u13}诱导出来,森林F2由边集{u1u9,u2u3,u3u4,u5u9,u6u7,u7u8,u10u12,u11u13}诱导出来,森林F3由边集{u2u6,u2u10,u4u8,u8u13,u9u12}诱导出来,形成3个线性2-森林.因此la2(H(13))≤3.要证明la2(H(13))̸=2.假设有相反的情况,有la2(H(13))=2.那么H(13)能被分解成两个线性2-森林.因为在H(13)中每一个线性2-森林最多包含⌊13/3⌋×2条边,接着在H(13)中两个线性2-森林包含最多16条边,这与E(H(13))=21相矛盾.所以,la2(H(13))=3.21 青海师范大学硕士学位论文u1u1u2uv1v9u69uu2u108v8v2v5u13u11u12v3v4vv76u3u5u3u4u5u6u7u4H(13)H(15)uu2uu23u163u16u4uu4u1515u5u14u5u14u1uuu1uu613613u7u12u7u12u8u11u8u11u9u10u9u10H(16)1H(16)2u2u2u3u16u3u16u4u15u4u15u5u14u5u14u6u13u6u1u13u1u7u12u7u12u8u11u8u11u9u10u9u10H(16)3H(16)4Figure1Hypohamiltoniangraphsoforder13,15and1622 阿贝尔群中给定度的凯莱图和Hypohamiltonian图的线性k荫度如果k=5,那么la5(H(13))≥2由引理2.2可得.根据引理2.1,可得la5(H(13))≤la4(H(13))≤···≤la2(H(13))=3.要证明la5(H(13))=3.假设,有相反的情况,使得H(13)能被分解成两个线性5-森林.因为每一个线性5-森林包⌊⌋含H(13)中最多13×5多条边,那么两个线性5-森林包含H(13)中最多20条边,6这与E(H(13))=21相矛盾.因此,la5(H(13))=3.由引理2.1可得,3=la2(H(13))≥la3(H(13))≥la4(H(13))≥la5(H(13))=3.所以,lak(H(13))=3如果2≤k≤5.情情情形形形3:6≤k≤12.如果k=6,那么根据引理2.2,有la6(H(13))≥2.显然森林F1由边集{u1u9,u2u6,u2u10,u3u11,u4u5,u4u8,u5u6,u7u12,u8u13,u9u11}诱导出来,森林F2由边集{u1u2,u1u8,u2u3,u3u4,u5u9,u6u7,u7u8,u9u12,u10u12,u10u13,u11u13}诱导出来,形成2个线性6-森林,因此la6(H(13))≤2.所以,la6(H(13))=2.对于k=12,根据引理2.2,la12(H(13))≥2.根据引理2.1,la12(H(13))≤la11(H(13))≤···≤la6(H(13))=2,因此la12(H(13))=2.根据引理2.1,得到2=la6(H(13))≥la7(H(13))≥···≥la12(H(13))=2.lak(H(13))=2如果6≤k≤12.§5.2阶为15的Hypohamiltonian图的线性k-荫度我们现在研究Hypohamiltonian图H(15)的线性k-荫度.命命命题题题5.2.设k是一个正整数.对于Hypohamiltonian图H(15),lak(H(15))=4,如果k=1;lak(H(15))=3,如果2≤k≤5;lak(H(15))=2,如果6≤k≤14.证明:我们分以下三种情形证明这个命题.情情情形形形1:k=1.根据引理2.3,可得la1(H(15))≥∆(H(15))=4.还需证明la1(H(15))≤4.显然,森林F1由边集{u1u2,u3u4,u5v7,v1v3,v2v5,v6v8}诱导出来,森林F2由边集{u1u6,u2v2,u4u5,v1v4,v5v8,v6v9}诱导出来,森林F3是由边集{u1v1,u2u3,u4v4,23 青海师范大学硕士学位论文u6v8,v3v5,v7v9}诱导出来,森林F4由边集E(H(15))(E(F1)∪E(F2)∪E(F3))诱导出来,它们形成4个线性1-森林,因此la1(H(15))=4.情形形形2:2≤k≤5.⌈⌉⌈⌉δ(H(15))+13+1如果k=2,那么根据引理2.2,得到la2(H(15))≥==2.那22么森林F1是由边集{u1u2,u1u6,u3v3,u4v4,u4v6,v1v3,v2v5,v5v7}诱导出来,森林F2是由边集{u1v1,u2u3,u3u4,u5v7,u6v8,v1v4,v6v8,v7v9}诱导出来,森林F3由边集E(H(15))(E(F1)∪E(F2))诱导出来,它们形成3个线性2-森林,因此la2(H(15))≤3.要证明la2(H(15))̸=2.假设有相反的情况,使得la2(H(15))=2.那么H(15)能被分解成两个线性2-森林.因为每一个线性2-森林包含H(15)中⌊⌋最多(15×2)条边,也就是说两个线性2-森林包含H(15)中最多20条边,这3与E(H(15))=24相矛盾.所以,la2(H(15))=3.如果k=5,根据引理2.2,可得la5(H(15))≥2.根据引理2.1,可得la5(H(15))≤la4(H(15))≤···≤la2(H(15))=3.要证明la5(H(13))̸=2.假设,有相反的情况,那么H(15)能被分解为两个线性5-森林.因为两个5-森林包含H(15)中最⌊⌋多(15×5×2+2)条边,接着两个线性5-森林包含H(15)中最多22条边,这6与E(H(15))=24相矛盾.因此,la5(H(15))=3.根据引理2.1,得到3=la2(H(15))≥la3(H(15))≥la4(H(15))≥la5(H(15))=3.所以,如果2≤k≤5,我们有lak(H(15))=3.情情情形形形3:6≤k≤14.如果k=6,那么根据引理2.2有la6(H(15))≥2.显然森林F1是由边集{u1u2,u1u6,u2u3,u3u4,u4v4,u5u6,v1v3,v2v5,v3v5,v6v8,v6v9,v7v9}诱导出来,森林F2是由边集E(H(15))E(F1)诱导出来,它们形成2个线性6-森林,因此la6(H(15))≤2.因此,可得la6(H(15))=2.对于k=14,根据引理2.2,可得la14(H(15))≥2.根据引理2.1,得到la14(H(15))≤la13(H(15))≤···≤la6(H(15))=2,因此la14(H(15))=2.推断出如果6≤k≤14，lak(H(15))=2.§5.3阶为16的Hypohamiltonian图的线性k-荫度在这一部分,我们研究Hypohamiltonian图Hi(16)的线性k-荫度(1≤i≤4).24 阿贝尔群中给定度的凯莱图和Hypohamiltonian图的线性k荫度命命命题题题5.3.设k是一个正整数.对于Hypohamiltonian图H1(16),{lak(H1(16))=5,如果k=1;lak(H1(16))=3,如果2≤k≤15.证明:我们分以下三种情形来证明这个命题.情情情形形形1:k=1.根据引理2.3,可以得到la1(H1(16))≥∆(H1(16))=5.还需证明la1(H1(16))≤5.显然,森林F1是由边集{u1u14,u2u3,u4u5,u6u7,u8u9,u11u12,u15u16}诱导出来的,森林F2是由边集{u1u11,u2u16,u3u4,u5u6,u7u8,u9u10,u14u15}诱导出来的,森林F3是由边集{u1u2,u4u12,u10u11,u13u14}诱导出来的,森林F4是由边集{u1u5,u3u10,u7u15,u12u13}诱导出来的,森林F5是由边集E(H1(16))(E(F1)∪E(F2)∪E(F3)∪E(F4))诱导出来的,它们形成5个线性1-森林.这意味着la1(H1(16))≤5,因此la1(H1(16))=5.情情情形形形2:k=2.因为∆(H1(16))=5,图H1(16)能被分解成至少三个线性2-森林,因此la2(H1(16))≥3.只需证明la1(H1(16))≤3.假设森林F1由边集{u1u5,u2u3,u2u16,u5u6,u7u8,u9u10,u10u11,u13u14,u14u15}诱导出来的,森林F2由边集{u1u2,u1u14,u3u4,u4u5,u6u7,u8u9,u11u12,u12u13,u15u16}诱导出来的,森林F3由边集{u1u8,u1u11,u3u10,u4u12,u6u13,u7u15,u9u16}诱导出来的,形成3个线性2-森林.这意味着la2(H1(16))≤3,因此la2(H1(16))=3.情情情形形形3:3≤k≤15.如果3≤k≤15,因为∆(H1(16))=5,两个线性k-森林不能分解H1(16).图H1(16)能被分解成至少三个线性k-森林,因此lak(H1(16))≥3.根据引理2.1,可得3=la2(H1(16))≥la3(H1(16))≥···≥la15(H1(16))≥3.因此如果3≤k≤15,lak(H1(16))=3.命命命题题题5.4.令k是一个正整数.对于Hypohamiltonian图H2(16),{lak(H2(16))=5,如果k=1;lak(H2(16))=3,如果2≤k≤15.25 青海师范大学硕士学位论文证明:我们分以下三种情形证明这个命题.情情情形形形1:k=1.根据引理2.3,得到la1(H2(16))≥∆(H2(16))=5.还需证明la1(H2(16))≤5.显然,森林F1由边集{u1u14,u2u3,u4u5,u6u7,u8u9,u11u12,u15u16}诱导出来,森林F2由边集{u1u11,u2u16,u3u4,u5u6,u7u8,u9u10,u14u15}诱导出来,森林F3由边集{u1u2,u4u12,u10u11,u13u14}诱导出来,森林F4由边集{u1u5,u6u10,u7u15,u12u13}诱导出来,森林F5由边集E(H2(16))(E(F1)∪E(F2)∪E(F3)∪E(F4))诱导出来,形成5个线性1-森林.这意味着la1(H2(16))≤5,因此la1(H2(16))=5.情情情形形形2:k=2.因为∆(H2(16))=5,两个线性2-森林不能分解H2(16).图H2(16)能被分解为至少三个线性2-森林,因此la2(H2(16))≥3.这显示出la2(H2(16))≤3.显然,森林F1是由边集{u1u5,u2u3,u2u16,u5u6,u7u8,u9u10,u10u11,u13u14,u14u15}诱导出来,森林F2是由边集{u1u2,u1u14,u3u4,u4u5,u6u7,u6u10,u8u9,u11u12,u12u13,u15u16}诱导出来,森林F3是由边集{u1u8,u1u11,u3u10,u4u12,u6u13,u7u15,u9u16}诱导出来,形成3个线性2-森林.这意味着la2(H2(16))≤3,因此la2(H2(16))=3.情情情形形形3:3≤k≤15.如果3≤k≤15,因为∆(H2(16))=5,两个线性k-森林不能分解H2(16).图H2(16)能被分解成至少三个线性k-森林,因此lak(H2(16))≥3.根据引理2.1,可得3=la2(H2(16))≥la3(H2(16))≥···≥la15(H2(16))≥3.因此lak(H2(16))=3,如果3≤k≤15.如果3≤k≤15,因为∆(H(16))=5,如果图H(16)能被分解成两个线性2-森林,必须出现3度点,所以图H(16)能被分解成至少三个l线性2-森林,因此la15(H2(16))≥3;根据引理2.1,有3=la2(H(16))≥la3(H(16))≥...≥la15(H(16))≥3所以la15(H2(16))=3,当2≤k≤15,lak(H2(16))=3.命命命题题题5.5.令k是一个正整数.对于Hypohamiltonian图H3(16),{lak(H3(16))=5,如果k=1;lak(H3(16))=3,如果2≤k≤15.26 阿贝尔群中给定度的凯莱图和Hypohamiltonian图的线性k荫度证明:我们分以下三种情形来证明这个命题.情形形形1:k=1.根据引理2.3,得到la1(H3(16))≥∆(H3(16))=5.还需证明la1(H3(16))≤5.显然,森林F1由边集{u1u14,u2u3,u4u5,u6u7,u8u9,u11u12,u15u16}诱导出来,森林F2由边集{u1u11,u2u16,u3u4,u5u6,u7u8,u9u10,u14u15}诱导出来,森林F3由边集{u1u2,u4u12,u10u11,u13u14}诱导出来,森林F4由边集{u1u5,u6u10,u7u15,u12u13}诱导出来,森林F5由边集E(H3(16))(E(F1)∪E(F2)∪E(F3)∪E(F4))诱导出来,它们形成5个线性1-森林.这意味着la1(H3(16))≤5,因此la1(H3(16))=5.情情情形形形2:k=2.因为∆(H3(16))=5,两个线性2-森林不能分解H3(16).图H3(16)被分解为至少三个线性2-森林,因此la2(H3(16))≥3.还需证明la2(H3(16))≤3.显然,如果k=2,因为∆(H(16))=5,如果图H(16)能被分解成两个线性2森林,一定会出现三度点,所以图H(16)能被分解成至少三个线性2-森林,因此la2(H3(16))≥3;又因为可以找到三个线性2-森林.森林F1由边集{u1u5,u2u3,u4u12,u2u16,u5u6,u7u8,u9u10,u10u11,u13u14,u14u15}诱导出来,森林F2由边集{u1u2,u1u14,u3u4,u4u5,u6u7,u6u10,u8u9,u11u12,u12u13,u15u16}诱导出来,森林F3由边集{u1u8,u1u11,u3u10,u4u15,u6u13,u7u15,u9u16}诱导出来,它们形成3个线性2-森林.这意味着la2(H3(16))≤3,因此la2(H3(16))=3.情情情形形形3:3≤k≤15.如果3≤k≤15,因为∆(H3(16))=5,两个线性k-森林不能分解H3(16).H3(16)能被分解成至少三个线性k-森林,因此lak(H3(16))≥3.根据引理2.1,可得3=la2(H3(16))≥la3(H3(16))≥···≥la15(H3(16))≥3.因此lak(H3(16))=3,如果3≤k≤15.命命命题题题5.6.令k是正整数.对于Hypohamiltonian图H4(16),{lak(H4(16))=5,如果k=1;lak(H4(16))=3,如果2≤k≤15.证明:我们分以下三种情况证明这个命题.27 青海师范大学硕士学位论文情情情形形形1:k=1.根据引理2.3,得到la1(H4(16))≥∆(H4(16))=5.还需证明la1(H4(16))≤5.假设森林F1由边集{u1u2,u3u4,u6u16,u8u9,u10u11,u12u13,u14u15}诱导出来,森林F2由边集{u1u14,u2u16,u3u7,u4u15,u5u6,u9u10,u11u12}诱导出来,森林F3由边集{u1u11,u3u10,u4u5,u7u8,u9u16,u13u14}诱导出来,森林F4由边集{u1u8,u3u13,u6u7,u12u16}诱导出来,森林F5由边集E(H4(16))(E(F1)∪E(F2)∪E(F3)∪E(F4))诱导出来,它们形成5个线性1-森林.这意味着la1(H4(16))≤5,因此la1(H4(16))=5.情情情形形形2:k=2.因为∆(H4(16))=5,两个线性2-森林不能分解H4(16).图H4(16)能被分解成至少三个线性2-森林,因此la2(H4(16))≥3.还需证明la2(H4(16))≤3.显然,森林F1由边集{u3u4,u3u7,u6u16,u1u8,u8u9,u10u11,u11u12,u13u14,u14u15,u2u16}诱导出来,森林F2由边集{u1u2,u1u11,u3u13,u3u10,u4u5,u5u6,u12u16,u15u16}诱导出来,森林F3由边集{u1u5,u1u14,u2u3,u4u15,u6u7,u7u8,u9u10,u9u16,u12u13}诱导出来,形成3个线性2-森林.这意味着la2(H4(16))≤3,因此la2(H4(16))=3.情情情形形形3:3≤k≤15.如果3≤k≤15,因为∆(H4(16))=5,两个线性k-森林不能分解H4(16).图H4(16)能被分解成至少三个线性k-森林,因此lak(H4(16))≥3.根据引理2.1,得到3=la2(H4(16))≥la3(H4(16))≥...≥la15(H4(16))≥3.因此如果3≤k≤15,有lak(H4(16))=3.28 阿贝尔群中给定度的凯莱图和Hypohamiltonian图的线性k荫度第六章总结与展望本论文研究了阿贝尔群中几类图的线性k-荫度问题,是图论中的重要问题,有重要的学术意义.论文主要研究了阿贝尔群中度为3,4的凯莱图和阶为13,15,16的Hypohamiltonian图的线性k-荫度,得到了一些新的结果.在本论文的基础上,我们还可以研究阿贝尔群上其它种类的凯莱图的线性k-荫度,研究阶为10,大于等于18的Hypohamiltonian图的线性k-荫度.29 青海师范大学硕士学位论文参考文献[1]S.B.Akers,B.Krishnamurthy,Agroup-theoreticmodelforsymmetricinterconnectionnetworks,IEEETrans.Comput.38(4)(1989),555566.[2]J.Akiyama,Threedevelopingtopicsingraphtheory,DoctoralDissertation,Univer-sityofToyo,1980.[3]R.E.L.Aldred,N.C.Wormald,Moreonthelineark-arboricityofregulargraphs,AustralasianJ.Combin.18(1998),97104.[4]N.Alon,Thelineararboricityofgraphs,IsraelJ.Math.62(3)(1988),311325.[5]N.Alon,V.J.Teague,N.C.Wormald,Lineararboricityandlineark-arboricityofregulargraphs,Graphs&Combin.17(1)(2001),1116.[6]J.C.Bermond,J.L.Fouquet,M.Habib,B.Peroche,Onlinear´k-arboricity,DiscreteMath.52(2-3)(1984),123132.[7]L.Babai,Automorphismgroups,isomorphism,reconstruction,in:R.L.Grahametal.(Eds.),HandbookofCombinatorics,ElsevierScience,Amsterdam,1995,14491540.[8]F.Bao,Y.Igarashi,S.R.Ohring,ReliableBroadcastinginProductNetworks,DiscreteAppl.Math.83¨(1998),320.[9]J-C.Bermond,O.Favaron,M.Maheo,HamiltoniandecompositionofCayleygraphsofdegree4,J.Combin.TheorySer.B.46(1989),142153.[10]N.Biggs,AlgebraicGraphTheory,CambridgeUniversityPress,NewYork,1992.[11]J.A.Bondy,U.S.R.Murty,GraphTheory,GTM244,Springer,2008.[12]N.J.Calkin,H.S.Wilf,Thenumberofindependentsetsinagridgraph,SIAMJ.DiscreteMath.11(1)(1998),5460.[13]G.J.Chang,Algorithmicaspectsoflineark-arboricity,TaiwaneseJ.Math.3(1)(1999),7381.[14]G.J.Chang,B.L.Chen,H.L.Fu,K.C.Huang,Lineark-arboricitiesontrees,DiscreteAppl.Math.103(1-3)(2000),281287.[15]B.L.Chen,K.C.Huang,Onthelineark-arboricityofKnandKn;n,DiscreteMath.254(1-3)(2002),5161.[16]S.K.Das,S.R.Ohring,A.K.Banerjee,EmbeddingsintohyperPetersennetwork:Yetanotherhypercube-¨likeinterconnectiontopology,VLSIDesign2(4)(1995),335351.[17]K.Day,A.-E.Al-Ayyoub,Thecrossproductofinterconnectionnetworks,IEEETrans.ParallelandDis-tributedSystems8(2)(1997),109118.[18]G.Dirac,OnHamiltoncircuitsandHamiltonpaths,Math.Ann.197(1972),5770.30 阿贝尔群中给定度的凯莱图和Hypohamiltonian图的线性k荫度[19]P.Fragopoulou,S.G.Akl,H.Meijer,Optimalcommunicationprimitivesonthegeneralizedhypercubenetwork,IEEETrans.ParallelandDistributedComputing32(2)(1996),173187.[20]H.Fu,K.Huang,C.Yen,Thelinear3-arboricityofKn;nandKn,DiscreteMath.308(2008),38163823.[21]R.Hammack,W.Imrich,SandiKlavzr,Handbookofproductgraphs,Secendedition,CRCPress,2011.˘[22]M.Habib,B.Peroche,Lak-arboricitelin´eairedesarbres,AnnalesPoloniciMathematici17(1983),307´317.[23]F.Harary,Coveringandpackingingraphs.I,AnnalsoftheNewYorkAcademyofSciences175(1970),198205.[24]M.C.Heydemann,Cayleygraphsandinterconnectionnetworks,in:G.HahnandG.Sabidussieds.,GraphSymmetry,KluwerAcademicPublishing,Dordrecht,1997,167224.[25]A.Itai,M.Rodeh,Themulti-treeapproachtoreliabilityindistributednetworks,Inform.Comput.79(1988),4359.[26]B.Jackson,N.C.Wormald,Onthelineark-arboricityofcubicgraphs,DiscreteMath.162(1-3)(1996),293297.[27]S.L.Johnsson,C.T.Ho,Optimumbroadcastingandpersonaizedcommunicationinhypercubes,IEEETrans.Computers38(9)(1989),12491268.[28]S.Lakshmivarahan,J.S.Jwo,andS.K.Dhall,SymmetryininterconnectionnetworksbasedonCayleygraphsofpermutationgroups:asurvey,ParallelComput.19(4)(1993),361407.[29]S.Ku,B.Wang,andT.Hung,Constructingedge-disjointspanningtreesinproductnetworks,ParallelandDistributedSystems,IEEETransactionsonparallelanddisjoitedsystems,14(3)(2003),213221.[30]R.Laskar,B.Auerbach,Ondecompositionofr-partitegraphsintoedge-disjointHamiltoncircuits,DiscreteMath.14(1976),265268.[31]K.W.Lih,L.D.Tong,andW.F.Wang,Thelinear2-arboricityofplanargraph,Graphs&Combin.19(2)(2003),241248.[32]J.Liu,HamiltoniandecompositionofCayleygraphsonAbeliangroupsofoddorder,J.Combin.TheorySer.B66(1996),7586.[33]Y.Mao,Path-connectivityoflexicographicalproductgraphs,Int.J.Comput.Math.93(1)(2016),2739.[34]Y.Mao,Z.Guo,N.Jia,andH.Li,Linek-arboricityinproductnetworks,JOIN16(3&4)(2016),1650008.[35]Wai-cheeShiu,On3-regularand4-regularCayleygraphsofabeliangroups,TechnicalReport,Dept.ofMathematics,HongKongBaptistUniversity,1995.[36]A.Vesel,J.Zerovnik,Onthelinear˘k-arboricityofcubicgraphs,Inter.J.Comput.Math.75(4)(2000),431444.31 青海师范大学硕士学位论文[37]B.Xue,L.Zuo,Linear(n1)-arboricityofKn(m),DiscreteAppl.Math.158(14)(2010),15461550.[38]C.H.Yeh,Lineark-arboricityofcompletemultipartitegraphs,ThesisforDoctorDegree,NationalChiaoTungUniversity,2005.[39]C.H.Yen,H.L.Fu,Linear2-arboricityofthecompletegraph,TaiwaneseJ.Math.14(1)(2010),273286.[40]S.Zhou,Aclassofarc-transitiveCayleygraphsasmodelsforinterconnectionnetworks,SIAMJ.DiscreteMath.23(2009),694714.[41]L.Zuo,S.He,andB.Xue,Thelinear(n1)-arboricityofCartesianproductgraphs,Appl.Anal.Discr.Math.9(1)(2015),1328.[42]R.E.L.Aldred,N.C.Wormald,Moreonthelineark-arboricityofregulargraphs,AustralasianJ.Combin.18(1998),97104.[43]N.Alon,Thelineararboricityofgraphs,IsraelJ.Math.62(3)(1988),311325.[44]N.Alon,V.J.Teague,N.C.Wormald,Lineararboricityandlineark-arboricityofregulargraphs,Graphs&Combin.17(1)(2001),1116.[45]J.A.Bondy,Variationsonthehamiltoniantheme,Can.Math.Bull.15(1)(1972)5762.[46]J.A.Bondy,U.S.R.Murty,GraphTheory,GTM244,Springer,2008.[47]G.J.Chang,Algorithmicaspectsoflineark-arboricity,TaiwaneseJ.Math.3(1)(1999),7381.[48]G.J.Chang,B.L.Chen,H.L.Fu,K.C.Huang,Lineark-arboricitiesontrees,DiscreteAppl.Math.103(1-3)(2000),281287.[49]B.L.Chen,K.C.Huang,Onthelineark-arboricityofKnandKn;n,DiscreteMath.254(1-3)(2002),5161.[50]V.Chvatal.Fip-flopsinhypohamiltoniangraphs,Can.Math.Bull.16(1)(1973)3341.´[51]J.B.Collier,E.F.Schmeichel,Systematicsearchesforhypohamiltoniangraphs,Networks8(1978),193200.[52]J.Doyen,V.vanDiest,Newfamiliesofhypohamiltoniangraphs,DiscreteMath.13(1975),225218.[53]T.Gaudin,J.C.Herz,P.Rossi,Solutionduproblemeno.29,Rev.Franc.Rech.Operat.8(1964),214218.`[54]M.Habib,B.Peroche,Lak-arboricitelin´eairedesarbres,AnnalesPoloniciMathematici17(1983),307´317.[55]F.Harary,Coveringandpackingingraphs.I,AnnalsoftheNewYorkAcademyofSciences175(1970),198205.[56]J.C.Herz,J.J.Duby,F.Vigue,Recherchesyst´ematiquedesgrapheshypohamiltoniens,Proc.1966Internl.´Symp.inRomeP.Rosenthiel,ed.,Dunod,Paris(1967)153160.32 阿贝尔群中给定度的凯莱图和Hypohamiltonian图的线性k荫度[57]W.F.Lindgren,Aninfiniteclassofhypohamiltoniangraphs,AmericanMath.Monthly74(1967)10871089.[58]Y.Mao,N.Jia,Z.Wang,E.Cheng,Lineark-arboricityofCaylaygraphsonAbeliangroupswithgivendegree,submitted.[59]R.Sousselier,Problemeno.29:Lecercledesirascibles,Rev.Franc.Rech.Operat.7(1963)405406.`[60]C.Thomassen,Hypohamiltonianandhypotraceablegraphs,Disc.Math.,9(1974)9196.[61]C.Thomassen,Onhypohamiltoniangraphs,Disc.Math.10(1974)383390.33 青海师范大学硕士学位论文致谢本学位论文是在我的导师冶成福教授的悉心指导下完成的,在论文完成之际,谨向冶老师致以衷心的感谢！冶老师渊博的专业知识,严谨的治学态度,精益求精的工作作风，诲人不倦的高尚师德,严以律己、宽以待人的崇高风范,朴实无华、平易近人的人格魅力对我影响深远.从导师那里学到的不仅是知识,更重要的是精益求精、学无止境的治学精神.思维敏锐,思想超前,治学严谨、为人谦和,这些都是我一生学习的楷模.在此谨向导师表示崇高的敬意和衷心的感谢!衷心地感谢毛亚平教授,毛老师一直带着我做论文.在论文的选题到完成整个创作过程中,毛老师倾注了大量的心血,从结构组织到撰写方法,甚至到论文的各个细节,都得到了毛老师的大力指导.毛老师严谨的治学精神和忘我的工作态度极大地激发了我的研究热情,将永远勉励我奋发向上.毛老师的这种对待学术的严谨和热情将使我受益终生.同时感谢给我授过课的所有老师.感谢他们传授我方方面面的知识，拓宽了我的知识面，开拓了我的视野.此外,衷心地感谢一起学习、生活的同学们以及对我关心与支持的师兄师姐师妹,正是因为有了你们的支持与帮助,才使我顺利完成学业.最后感谢我的父母和家人对我的生活和学习给予莫大的关心与支持.他们无私的奉献使我能够全身心地投入到学习和研究中去.贾楠2018年3月6日34 阿贝尔群中给定度的凯莱图和Hypohamiltonian图的线性k荫度个人简介姓名:贾楠性别:女民族:汉出生年月:1992.3.16籍贯:山西省运城市稷山县政治面貌:中共党员学习经历2009年9月――2013年7月就读于山西师范大学现代文理学院数学与计算机学院,获理学学士学位.2015年9月――2018年7月就读于青海师范大学数学与统计学院,攻读理学硕士学位.在校期间所获荣誉2015――2016学年获得奖学金二等奖.2016――2017学年获得奖学金三等奖.2017年5月获得青海师范大学“优秀研究生”.2017――2018学年获得奖学金一等奖.研究成果已已已发发发表表表:1.Y.P.Mao,Z.Guo,N.Jia,H.Li,Linek-arboricityinproductnetworks,JOIN16(3&4)(2016),1650008.(EI)2.N.Jia,J.Yin,C.Wang,X.Wang,Lineark-arboricityofHypohamiltoniangraphswithsmallorder,IEEEComputerSocietyISPAN-FCST-ISCC201766-70.(EI)已已已接接接收收收:1.N.Jia,Z.Wang,YXiao,J.Yin,GeneralizedNordhaus-Gaddumtyperesults35 青海师范大学硕士学位论文forgeneralRandi′cindexandgeometric-arithmeticindexofgraphs,acceptedbyJournalofCombinatorialMathematicsandCombinatorialComputing.(EI)2.Z.W.GuoY.P.Mao,N.Jia,H.Li,StrongEquitableVertexArboricityinCarte-sianProductNetworks.已已已完完完成成成:1.Y.P.Mao,N.Jia,Z.Wang,E.Cheng,Lineark-arboricityofCaylaygraphsonAbeliangroupswithgivendegree.36