禁用子图与图的路圈性质

《禁用子图与图的路圈性质》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、独创声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得（注：如没有其他需要特别声明的，本栏可空）或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文作者签名：王．王嗣ｔ学位论文版权使用授权书本学位论文作者完全了解堂燕有关保留、使用学位沦文的规定，有权保留并向国家有关部门或机构送燹论文的复印件和磁盘，允许论文被查阅和借阅。本人授权—堂盟可以将学位论文的全部或部分内容编入有关数据库

2、进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。（保密的学位论文在解密后适用本授权书）学位论文作者签名：王王丽签字日期：２００６年埠月№目导师签字签字日期：２００洲６年斗月『ｏ日剥程毛洲山东师范大学硕士学位论文禁用子图与图的路圈性质（山东师范大学数学科学学院，济南，ｌｌ』东，２５００１４）摘要路和圈是图的两个基本结构，是分析、刻画图的整体结构的有力工具．大量的实际问题都可以归结为图的路和圈的问题．对图的路圈性质的研究是在图论中的著名问题一一哈密顿问题的基础上发展而来的．关于图的哈密顿圈的研究，己经取得了长足的发展，这方面的研究成果和进展情况可参见文献【ｎ］一［７］对

3、图的路和圈性质的研究一直是图论中的热门领域，经过几十年的发展，图的路圈性质所涉及的内容日益丰富和具体。路的方面包括图的哈密顿路（可迹性）、最长路、Ｈａｍｉｌｔｏｎ连通、泛连通、路可扩等等；圈的方面包括图的哈密顿圈、最长圈、（点）泛圈、完全国可扩等等由于直接研究‘般图的路圈性质比较困难，若干年来相关的研究主要集中在一些特殊图类上，即不含某些禁用子图的图类．其中比较有代表性的是无爪图，它是以Ｋ。为禁用子图的图类，研究该图类的最初动机来源于Ｄｅｉｎｅｋｅ所给的线图的性质［８］｛９】ｊ上个世纪八九十年代对无爪图的研究成为图论中的著名课题，至今在这方面已取得了相当多的研究成果．在此基础上，人们将研

4、究图类逐渐拓宽至几乎无爪图、爪心独立图、半无爪图、（Ｋｌｐ；ｇ）一图等等．这些图类或是无爪图的推广，或与无爪图有密切联系，近年来其它一些新型的禁用子图也不断被提出．本文就是研究某些禁用子图与图的路圈性质．第一章主要介绍本文的研究背景和相关结论，以及文章所涉及到的一些基本概念和术语符号．第二章主要研究半无爪图的可迹性这～章分为四个小节，在５２１节介绍了半山东师范大学硕士学位论文无爪图的概念和研究成果，５２２，５２３ｊ５２４节分别给出了本章的三个主要定理引理２。２．１设Ｇ是礼阶连通半无爪图．Ｐ是一条长为？的路（３茎ｒ＜ｎ），如果Ｇ不含长为ｒ＋１的路，则对ＶⅡｚ∈Ｅ（ｙ（Ｐ），

5、ｙ（Ｇ）一矿（尸）），有“一“＋∈Ｅ（Ｇ）引理２．２．２设Ｇ是礼阶连通半无爪图，Ｐ是Ｇ的一条最长路（１ｐＩ＜¨），日是Ｇ～Ｐ的一个连通分支，ｕｚ，＂ｇ∈Ｅ（矿（Ｐ），ｙ（日））（“，口∈Ｖ（Ｐ）；ｚ，可∈Ｖ（日）），那么（。）ｕｇ（ｕ一，ｕ２，＂，ｕ＋，＂州，ｕ书）（ｂ）＂一，矿：”～ｊ口＋２岳ｊｖ（ｕ）（ｃ）Ｅ（｛趾一，ｕ一２），（＂一，＂１２））＝０＝Ｅ（｛“＋，ｕＴ２），｛ｕ＋：＂＋２））定理２．２．３引理２．３．１若Ｇ为佗阶２。连通半无爪图，满足Ⅳａ≥堡笋，则Ｇ是可迹的．设Ｇ是连通半无爪图，＂∈、厂（Ｇ），Ｐ是Ｇ中‘条最长的＂一的路，ｕｚ∈Ｅ（Ｖ（Ｐ）一（ｕ），Ｖ（Ｇ—Ｐ））

6、（ｕ∈矿（Ｐ），ｚ∈ｙ（Ｇ—Ｐ））：则¨一“１∈Ｅ（Ｇ）迹的定理２．３．２定理２．４若Ｇ为ｎ阶３一连通半无爪图，满足ⅣＧ三罕，则图Ｇ是齐次可若Ｇ为ｎ阶２一连通半无爪图，满足Ⅳｃ三％墨，则图Ｇ是齐次可迹的．第三章主要研究（甄，，；ｑ）一图扫＝４，ｇ＝１，２）的路性质这一章分为三个小节，５３．１节主要介绍（Ｋ１，ｐ；ｇ）一图的概念及研究状况，§３２节研究（Ｋｌ，４；１）一图的３一ｗａｌｋ，５３．３节研究（Ｋｌ，４；２）一图的路可扩性，所得到的主要定理如下：引理３．２．１没Ｇ是一个Ｋ１．４一，ｒｅｅ图，ｚ∈Ｖ（Ｇ）；Ｇ是Ｇ的一个ｃｏ口ｅｒ犰９Ⅲ酬☆如果ｙ（ｚ，ａ）≥４，则存在一个ｃ。ｕｅ

7、ｒｚ礼９Ⅲｏ｛ｋｃ７使得ｆ（∥）≤ｃ（Ｇ）一１，Ｖ（ｚ，Ｇ’）＝矿（ｚ，Ｃ，）一ｌ并且对任意的ｇ∈Ｖ（Ｇ）（ｇ≠ｚ）有＂（目，Ｇ７）≤矿（玑ｃ）．推论３．２．２每一个连通的匮．４一，ｒｅｅ图的最小ｃｏ＂ｅｒｉ叼ｔ￡Ｊａｆ女是一个３一山“№推论３．２．３每一个连通的Ｋ１，４一，ｒｅｅ图都有一个３一Ⅲｏ隐推论３．２．４在连通的Ｋｌ，４一，ｒｅｅ图中，如果存在一个ｃ。＂ｅｒｚｎｇ叫ｎｆ克通过贯点ｎ（＂曼３）次，那么一定存在一个３一州ｏｆ