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

《阿贝尔群中给定度的凯莱图和Hypohamiltonian图的线性k荫度.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号密级公开UDC学号20150713012青海师范大学硕士学位论文阿贝尔群中给定度的凯莱图和Hypohamiltonian图的线性k荫度研究生姓名贾楠导师姓名(职称)冶成福，教授申请学位类别硕士学位学科专业名称应用数学研究方向名称组合数学与图论论文提交日期2018年3月论文答辩日期2018年5月学位授予单位青海师范大学学位授予日期2018年6月答辩委员会主席李学良评阅人专家一，专家二阿贝尔群中给定度的凯莱图和Hypohamiltonian图的线性k荫度中文摘要线性k-森林是每个分支都是长度不超过k的路.一个图G的

2、线性k-荫度,用lak(G)表示,是指分解G需要的最小的线性k-森林的个数.线性1-森林是由一个匹配诱导出来的.图的线性k-荫度的概念由Habib和Peroche提出,是边着色定义的一个自然推广.用la1(G)来表示一个图G的线性1森林,分支是路长不超过1的路,就等价于图G的边着色数χ′(G).线性k-森林是普通线性荫度的一个细化,la(G)(或者la∞(G))表示每个森林的每个分支都是路长不受限制的.图的线性k-荫度是图的着色理论和分解理论中的重要概念.近年来在国内外得到了广泛的研究.本文研究了阿贝尔群中度为3和4

3、的凯莱图以及阶为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、第四章主要研究关于阿贝尔群上的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上的单位元素.

5、X上的凯莱图Cay(X,A)是一个简单图,其顶点集为X,边集为E={xy

6、x−y∈A}.在循环群中一个循环图就是凯莱图.Cay(X,A)是连通的当且仅当A是由X生成的.多年来在代数学图论中凯莱图都是重要的研究对象,许多数学和计算机科学家用凯莱图作为网络交流I的模型.事实上,在具备理论和实践重要性的网络数目上,包括超立方体,蝴蝶图,立方-连通圈,星图和它们的推广,都是凯莱图.若图G不是哈密顿图,且对于v∈V(G),G−v是哈密顿图,则称G为Hypohamiltonian图.关关关键键键词词词:线线线性性性k-森森森林林

7、林,线线线性性性k-荫荫荫度度度,凯凯凯莱莱莱图图图,Hypohamiltonian图图图.IILineark-arboricityofCaylaygraphsonAbeliangroupswithgivendegreeandHypohamiltonianGraphsAbstractAlineark-forestisaforestwhosecomponentsarepathsoflengthatmostk.Thelineark-arboricityofagraphG,denotedbylak(G),istheleas

8、tnumberoflineark-forestsneededtodecomposeG.Clearly,alinear1-forestisinducedbyamatching.Thenotionoflineark-arboricityofagraphwasfirstintroducedbyHabibandPeroche,whichisanaturalgeneralizationofedge-coloring.la(G)isthechromaticindexχ′(G)1ofagraphG.Moreover,thelinea

9、rk-arboricitylak(G)isalsoarefinementoftheordinarylineararboricity.la(G)(orla∞(G))whichisthecasewheneverycomponentofeachforestisapathwithnolengthconstraint.Thelineark-arborici