图线性荫度和点荫度

《图线性荫度和点荫度》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中文摘要本论文研究了图的线性荫度和点荫度问题，文中所涉及的图均为有限简单图．图G的点荫度Ⅷ(G)是由chanraIld，l①11l【和wall【13】最早提出来的。图G的线性荫度的概念最早是由Harary在[12]中提出来的．用肠(G)和△(G)分别表示图的线性荫度和最大度．在线性荫度的研究中有一个非常著名的线性荫度勰对撕的简单配有『竽恤G，可掣]．在第一章中，我们较为详细地介绍了本文的一些背景知识，所用到的基本概念以及主要结论．在第二章中，我们首先给出了三次方图的定义：任意两点“，1，∈y(G)，它们之间的距离指的是这两点之间的最短路的长度，我们用dG(“，v)来表示．在图

2、G的三次方图G3中，矿(G3)=矿(G)，E(G3)={洲：扰，V∈H回，甜≠V，％(“，V)≤3)．接着讨论了当图G的最大度为砒其三次方酣的点荫度满足『-竽]洲G3)<

3、半1．最后对圈e的三次方图q的点荫度进行了研究．在第三章中，我们考虑了平面图的线性荫度问题，讨论了不含3一圈的平面图的结构特点，并且证明了△(G)=7且不含3一圈的平面图满足线性荫度猜想．关键词：图；线性荫度；三次方图；点荫度分类号：0157．5ABSTRACTIn“smesis，westudythe1ineararboricityaIldthevenexarboricityof黟aphsa11dall黟印

4、hsconsideredmt11ispaperarefinitesimple黟aphs．Thevertex．抽oncityⅧ(G)ofa铲aphGwaSfirstintroducedbychamand，Kronka11dWall【131．Theconc印tof1ineararbodcitywaSintroducedfirstbyHararyin[12】．Let肠(G)aIld△(G)denotetllelineararboric埘andmemaximumde铲eeofagraphG．Tlle劬d锄entalquestioniIlmes硼yoflinear抽oricityisa

5、conjecture：For锄y『．竽bG，可掣IIlchapterl，weintroducesomebasicnotionsusediIltllismesis，舀Veachiefsurveyont11isdircctionandmainresultsintllemesis．Inch印ter2，we6rstin仃oducetheconceptofmecubic铲aphG30fa黟aphG：Let觚oVenices“，V∈y(G)，thedistaJlcebetween“aIldy，denotedbydG(“，V)，ist11elengthofmesmallestpambe觚e

6、enuandV．The吐1r．eccubed铲印hG30fa铲aphGisⅡle莎aphde6nedon矿(G3)=y(G)，E(G3)={圳：“，v∈y(G)，甜≠v’吒(“，v)≤3)．Let△denotememaXimumde铲eeofa黟aphG，Thenmevertexarboricityoft11e黟印hs⋯s⋯n叩舭阿洲G3，可△3一△2+△+12．Finally’Letc：denotemeⅡ1reecubed孕叩hofcycleC。，Wbstudy廿1evenexarboricityof111chapter3，westudythelineararboricit

7、yofplanar伊aphs．ItisproVed廿1atLinear心boricityConjecn鹏h01dsforplanar孕aphswith△(回=7andwimout3-cycles．KEYWoRDS：孕印h；1ineararboricity；t11reecubed铲aph；VerteXarboricity．CLASSNo：0157．5．1V致谢两年的研究生学习时光已经接近尾声，在此我非常感谢培养我的北京交通大学，这里浓厚的学术氛围，舒适的学习环境我将终生难忘!本论文的工作是在我的导师何卫力老师的悉心指导下完成的，何卫力老师渊博的专业知识，严谨的治学态度和科学的工

8、作方法，朴实无华、平易近人的人格魅力都对我影响深远。在此衷心感谢两年来何卫力老师对我的关心和指导。此外，本文最终得以顺利完成，也是与理学院其他老师的帮助分不开的。郝荣霞老师对于我的科研工作和论文都提出了许多的宝贵意见，在此表示衷心的感谢。在撰写论文期间，我的同学朱锡媛、高西娜、师琳娜、全珍旭、王可可，师兄石淼、金政国对我论文中的研究工作都给予了热情帮助，在此特向他们表达我的感激之情。还要感谢的是我的父母，他们为我能够顺利完成毕业论文提供了巨大的支持与帮助。最后，对为本文审阅的和参加笔者论文答辩的专家教授