（基础数学专业论文）一类无爪图的几个性质.pdf

摘要 本文主要对。类无爪图进行了讨论，得出了如下的一些结果： ( 1 ) 若g 是无瓜连通图，m ( g 1 2 x l x e v ( o ) ，z 局部连通 是g 的一个控 制集，( 肘( g ) ) 有两个分支，设为m ，m z ，则c ，( g ) 是完全图当且仅当g 中存在连 接这两个分支的圈c ，且c 上存在非局部连通点x ，使得如( x ) 2 ，电( x ) 2 ， 其中q = ( 矿( m ) u ( m ) ) ， ) = l g ( z ) n y ( q ) 1 ( 2 ) 若g 是无爪连通图，m ( g ) - x l x v ( g ) ，x 局部连通 是g 的一个控制 集，( m ( g ) ) 有三个分支，设为m ，m z ，坞，则“( g ) 是完全图当且仅当g 满足 下列条件之一：( i ) g 中存在连接m ，鸩，鸩的圈c ，c 上有三个非局部连通的点； ( i i ) 至少存在，m ，使得( 矿( 瓯) u 矿( g ，) ) 满足( 1 ) 的条件且帝在连 接峨，m ，与鸭的圈c ，c 上存在蜚局部连通点工使得吱，) ) ( x ) 2 ， 电( x ) 2 ，其中q = ( 矿( m ) u ( m ) ) ，屯( x ) = i ( x ) n 矿( g 1 ) 1 并对肘( g ) ) 有，个分支时进行了推广 ( 3 ) 若g 是无爪连通图，m ( g , ) x i x e v ( g ) ，x 局部连通) 是g 的个控 制集，( 膨( g ) ) 有两个分支，设为m ，肘：，若c ，( g ) 是完全图，则g 是泛圈的 ( 4 ) 若g 是无爪连通图，厨( g ) - = x l x e v ( g ) ，x 局部连通) 是g 的一个控 制集，( m ( g ) ) 有三个分支，设为m ，鸩， 毛，若d ( g ) 是完全图，则g 除一种情 况外是泛圈的 ( 5 ) 给出了( ”) 的一个新的下界，其中c 。( h ) 为g 中不包含长为i 的圈，这 些f ( 3 i - l o ，gh a v ea tl e a s tav e r t e xx ，( 心( x ) ) i sn o t i c e a i l yc 。n n e c t e do r ( 心( ) ) i sc o m p l e t e d ，吖( g ) = x i x 矿( g ) ，x i sl o c a l l y c o n n e c t e d i sad o m i n a t i n gs e t o fg ，a n d ( 埘( g ) ) i sc o n n e c t e d ，t h e n gh a s 2 f k t o r w i t ht w o c o m p o n e n t s ，m o r e o v e r , 旧 l o i st h eb e s tp o s s i b l e k e y w o r d s ：c l a w - f r e eg r a p h ；c l o s u r e ；p a n c y c l i c ；d o m i n a t i n gs e t ；2 - f a c t o r 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他入已经发表或撰写过的研究成果，也不包含 为获得或其他教育机构的学位或证书而使用过的材科与我一同工作 的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表 示谢意 学位诊骞作者签名：主稆鑫签字日期：刀，7 f 年穸月刁日 学位论文版权使用授权书 本学位论文作者完全了解江西师范大学研究生院有关保留、使用 学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许论文被查阅和借闲本人授权江西师范大学研究生院 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印，。缩印或扫描等复制手段保存、汇编学位论文 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：宴始签 签字日期：砷年f 月刁日 导师始割脓】坞导师签名：刚广琴r 匀 签字日期：唧年厂月巧日 一类无爪图的几个性质 第一章引言与预备知识 1 1 引言 近几十年来，无爪图成为许多学者感兴趣的研究课题之一对无爪图性质的研 究首先是由b e i n e k e 在 7 0 1 ，【7 l 】中研究线图的性质引起的，但是，将更多图论学者 的注意力转移到无爪图的研究是在7 0 年代末8 0 年代初，在这个时期，在【2 】，【3 】，【4 】 中对无爪图的匹配性质进行了研究，在【5 】，【6 ， 7 1 ，【8 】中证明了无爪图的哈密顿性 质但最重要的是证明了在无爪图中确定独立数的算法是多项式次的，且b e r g e 的 完美图猜想在无爪图中是成立的 到目前为止，关于无爪图的结果有很多： 首先，确定了有一些常见和重要的图类它们是无爪图，例如：( 1 ) 线图；( 2 ) 无三角图的补图，因为图g 是无三角图的补图当且仅当它的独立数d ( g ) 2 ； ( j ) 一个图g 的膨胀( i n f l a t i o n o f g r a p h ) ，即将g 中的每个顶点，用阶为d ( x ) 的 完全图代替且与x 相连的每条边分别与这个完全图的一个不同顶点相连；( 4 ) 可 比图( c o m p a m b l i t yg r a p h ) 即考虑实数域上有限区间的集合，使得不存在一个集 合完全包含另一个集合，如果一个无爪图，它的顶点集为这些区间的集合，两个 顶点之间有边当且仅当这两个区间的交集非空，则称为可比图；( 5 ) 中间图， ( m i d d l e g r a p h ) 图g 的中间图是将顶点插到每条边e ( t f s e ( g ) ) t 且增加边 葺一( i i , j e ( g ) ，f _ ，) 当且仅当p 与巳有一个公共端点，每个图的中间图都是 无爪图；( 6 ) 广义的线图，即图的每个顶点的邻域都最多可划分为两个团 其次，对无爪图的概念进行了推广，例如定义了无k ，图，局部无爪图，几 乎无爪图，一图( 一个图g 称为厶一图，如果对每三对顶点“，v ，w d ( u ，v ) = 2 ，w e ( “) n ( v ) ，有d ( “) + j ( v ) 阿( “) u ( v ) u ( w ) 卜_ i ，d ( u ，v ) 指 “，v 问的距离) ，等等 再次，通过对图的一些量进行分析来研究无爪图的性质例如，对度数、邻域 条件及连通性的分析对无爪图的哈密顿性、泛圈性、可迹性进行了研究，其结果 可参见文献 7 】、【9 】、 1o 】、【ll 】等；通过局部连通条件的分析得出了关于无爪图 一类无爪| 冬i 的几个性质 顶点泛圈可序性、圈可扩性、泛连通性、一哈密顿性等的结果，可参见文献 8 】、 【2 5 】一【3 1 】等；在文献【2 】、【3 】、【1 8 卜一【2 3 等中，对无爪图的匹配和因子进行了研 究；r e j a c e k 在文献 3 4 1 中提出了无爪图闭包的概念，利用闭包的性质对无爪图 进行了研究，等等 最后，在得到无爪图许多结果的同时也提出了许多猜想和问题，例如； 猜想1 ”1 若g 是4 连通无爪图，则g 是哈密顿的 猜想2 “0 1 若g 是2 连通无爪图，则g 有t u t t e ，圈 猜想3 。”若g 是阶至少为4 的连通、局部连通无爪图，则g 是泛连通的当且 仅当g 是3 连通的 猜想4 1 若_ ，2 l ，k 2 ，g 是，一连通且无k m 图，则g 有一条一w a l k 等等 所以，对无爪图，我们还应该进行更深入的研究本文主要对一类无爪图进 行了研究，首先是研究了这类无爪图的闭包，然后利用闭包的性质研究了这类无爪 图的几个性质 1 , 2 预备知识 本文考虑的图g = ( 矿( g ) ，e ( g ) ) 是有限无向简单图，未定义的术语和符号参 见文献【l 】 ， 定义1 1 对图g ，一个生成子图h 同构于k ，称为图g 的爪；图g 称为 无爪图如果它不包含爪g 是无爪图当且仅当对任意的x v ( g ) t ( ( ( j ( x ) ) ) 2 ，其中。( ( j ( x ) ) ) 表示( 。( x ) ) 的独立数 定义1 2 对s c 矿( g ) 我们记p ) 。为s 在g 中的生成子图，在不引起混淆 的情况下g 可省掉不写 定义1 3 我们称s c 矿( g ) 为g 的控制集，若矿( g ) 、s 中的每个点在5 中都 有邻点 定义1 4 对顶点x 矿( g ) ，集合( x ) = y e 矿( g ) x y e ( g ) ) 称为x 在 g 中的邻域：对集合【，c - v ( o ) 集合( u ) = ( u m ；( “) ) u 称为u 在g 中的邻 一类无爪州的几个性质 域设g7 是g 的一个子图，为叙述方便我们称集合 0 ，0 ) = 名( x ) n 矿( g 7 ) 为x 在 g 中的邻域，记办一( x ) = j ( j ( 工) n 矿( g ，) j 定义1 5 图g 称为哈密顿的，若g 中包含长为l 矿( g ) i 的圈m g 称为可迹 的( t r a c e a b l e ) 若g 中包含哈密顿路，即长为l 矿( g ) l l 的路 定义1 6 若g 中包含所有长为，的圈，其中3 ，f 矿( g ) | r c j 称, g 是泛圈 的， 定义i 7 对顶点x v ( g ) ，若( 。( x ) ) 是连通图，则称x 是局部连通顶点 定义1 8 在无爪图g 中，顶点x 称为合格的( e l i g i b l e ) 如果x 局部连通且 ( 心( x ) ) 非完全图若x 局部连通且( 心( x ) ) 为完全图，称工为单纯点 ( s i m p l i c i a l ) 若图g 中的点都是局部连通点，则称g 是局部连通的对合格顶 点z y ( g ) ，把( ( z ) ) 中不相邻的点连接起来的操作称为对x 进行局部完全化， 通过对x 进行局部完全化所得的图记为g ， 定义1 9 ；g g 是无爪图，称日是g 的闭包，记h = c t ( g ) ，如果 ( 1 ) 存在序列g ，g 2 q 和顶点一，x 2 ，x j 使得g ，= g ，g ，= h ，x ，是e 中的合格点，q + ，= ( g ) 。；f = l ，2 ，t ，- - i ； ( 2 ) 日中不存在合格点 定义1 1 0 令c 是无爪图的一个子类，我们称c 对于闭包是稳定的，如果对每 个g c ，c ，( g ) c ；称性质纯类c 中对于闭包是稳定的，如果g c 有性质p 当且 仅当c t ( g ) c 也有性质p 定义1 1 l 图g 称为顶点泛圈的若对g 的每个顶点x ，都存在所有包含x 的 长为，的圈，3 ，p ( g i 我们说g 有一个泛圈序，若g 的顶点有一个序使得对 任意，( 3 s s l y ( g ) 1 ) ，前j 个顶点的生成子图是哈密顿的g 是项点泛圈可 序的，若对g 中的每个项点z 。矿( g ) 有一个泛圈序使得x 是这个序的第一个顶 点， 显然，每个顶点泛圈可序图是顶点泛圈的，每个顶点泛圈图是泛圈图 一类无爪蚓的几个性质 定义1 1 2 一个幽c c g 是可扩的，若存在c 亡g ( 称为c 的扩展) 使得 v ( c ) c v ( c ) 且lv ( c ) i = lv ( c ) i + l ，若边叫t e ( c ) ，墨y v ( c ) 则称边矽 为c 的弦一个圈c7 c g 是c 的k - 弦扩展若c7 是c 的个扩展且e ( c ) 最多包 含c 的k 条弦 定义1 1 3 若s c v ( g ) 是连通图g 的一个割集( 也就是说g s 不连通) 使 得( s ) 。是一个团，我们称s 是gt y j - + 团害j j 定义1 1 4 网( t h en e t ) 记为指唯一以3 3 3 1 l l 为度序列的图无c n 图是指不包含爪和刚为生成子图的图 下面介绍一些关于无爪图的结果，我们都把它们称为定理： 定理1 1 令g 是一个无c 图，则1 ) 若g 是连通的，则g 是可迹的； 2 ) 若g 是2 - 连通的，则g 是哈密顿的 注由观察很容易得到，在无爪图g 中，坛y ( g ) ，( 6 ( x ) ) 是无网的， 又因为( 。( x ) ) 是无爪的，由定理1 1 有如下的结论：若x 非局部连通，则( ：( x ) ) 由两个顶点不交且不连通的团覆盖；若( g ( x ) ) 的连通度为l ，则( j ( x ) ) 是可迹 的且( ：o ) ) 可由两个顶点不交的团覆盖使得连接这两个团的边在其中一个团 中有个公共端点；若( 心( x ) ) 是j i 连通的( t 2 ) ，则( g ( x ) ) 是哈密顿的 定理1 2 1 设g 是连通无爪图，a ( g ) 3 ，则g 的每个顶点，满足下列条件 之一：i ) n ( v ) 可由两个完全图覆盖： 2 ) n ( v ) 包含c ，为生成子图 定理1 3 。”令g 是无爪图，x 是合格点，则 1 ) 图g 是无爪图： 2 ) f ( q ) = c ( g ) ，其中c ( g ) 为g 的周长，即g 中最长圈的 长度 定理1 4 嘲令g 是无爪图，则 1 ) g 的闭包是唯一的； 4 类无爪| 冬| 的几个性质 2 ) c ( g ) = c ( d ( g ) ) 注定理1 4 的1 ) 表明g 的闭包d ( g ) 不依赖于对合格点进行局部完全化的 顺序；由2 ) 可知无爪图g 是哈密顿的当且仅当f ，( g ) 是哈密顿的 定理1 5 。嗣若g 是无爪图，工邻域的生成子图是团，则c ，( g ) 是完全图当 且仅当c l ( g - x ) 是完全图 定理1 6 嘲对任意七2 ，存在t 连通无爪图g ，g 不是泛圈的，c l ( g ) 是泛圈的 定理1 7 删设g 是一个无爪图，ccg 是一个圈，假定有一个顶点 v v ( c ) ，使得( v ) 、矿( c ) ；o ，且( ( v ) ) 是连通的，则存在c ，cg ，矿( c ) c v ( c ) u ( v ) r c 是c 的一个2 弦扩展 ： 定理i 8 删若g 是无爪连通图，m ( g ) - x l x 毫v ( g ) ，x 局部连通) 是g 的 一个连通控制集，则g 是顶点泛圈可序的， 定理1 9 蚓若g 是无爪连通图，m ( g ) = x i x v ( g ) 。x 局部连通 是g 的 一个连通控制集，则c ，( g ) 是完全图 定理1 1 0 嘲若g 是无爪图，s c v ( o ) 是6 的一个团割，记e ，放玩为 g - s 的分支，令s = 缈( 耳) ) n s ，g f = ( 矿( q ) u s ) 。假设晦 2 ，i = 1 七，则 c t ( g ) 是完全图当且仅当d ( q ) 是完全图，f - l ，k 一类无爪 冬| 的几个性质 第二章一类闭包是完全图的无爪图 2 1 、引言 无爪图的闭包是由r y j a c e k 在 3 4 】中提出来的，由预备知识可以知道，无爪 图的闭包是唯一决定的，无爪图的闭包操作将无爪图变成一个无三角图的线图， 并且保持了圈和路的一些性质，这些事实使无爪图的闭包成为改进无爪图许多结 论的一个工具本章主要介绍一类无爪图它的闭包是完全图 2 2 、主要结果及其证明 i 、王要结果 定理2 1 若g 是无爪连通图，肘( g ) = x l x v ( g ) ，x 局部连通 是g 的一个控 制集，i m ( g ) ) 有两个分支，设为肘，肘：，则c ，( g ) 是完全图当且仅当g 中存在 连接这两个分支的圈c ，且c 上存在非局部连通点x ，使得屯( x ) 2 ；屯( x ) 2 2 ， 其中q = ( 矿( m ) u ( m ) ) ，如( 工) = l g ( x ) n 矿忙) 1 定理2 2 莓g 是无爪连通图，m ( g ) = z k 矿( g ) ，x 局部连通，是g 的一个控制 集，( m ( g ) ) 有三个分支，设为， 屯，m 3 ，则c ，( g ) 是完全图当且仅当g 满足下 列条件之一： 一， ( 1 ) g 中存在连接鸩，鸩， tn n c ，c 上有三个非局部连通的点； ( 2 ) 至少存在m ，m ，使得( y ( q ，) u y ( g l ：) ) 满足定理2 1 的条件且存在连接 m ，m ，与m ，n n c ，c 上存在非局部连通点x 使得t ，( a ，州吒) ) ( x ) 2 ， 吃，( x ) 2 ，其中g = ( 矿( m ) u ( m ) ) ，屯( x ) = i g ( x ) n 矿( g ) | 推论若g 是无爪连通图，肘( g ) = x i x v ( g ) ，x 局部连通) 是g 的一个控制 集，( m ( g ) ) 有，个分支，设为m 。，m ：m ，若任意一对m ，时，( f ，) 都有 妒( q ) u y ( g m 满足定理2 1 的条件，则c f ( g ) 是完全图 一类无爪i 鍪| 的几个性质 2 、结果证明 引理2 1 若g 是无爪连通图，对v ( g ) 中的合格点x 进行局部完全化后，若 ( g ) ) 连通，则( p ) ) 连通 证明情形i y g g ( x ) 若i ( x ) n u j y ) l 2 ，对x z - 一，一全化后， ( 吼) ) 可由在( 心( y ) ) 中加边得到，加边不改变图的连通性，所以( 乞( y ) ) 连 通：若1 g ( x ) n ( y ) i s l ，则( g 。( y ) ) = ( g p ) ) ，所以( k o ) ) 连通 情形2 y e n a ( x ) ， 我们用反证法来证明假设( k ( y ) ) 不连通，不妨 设 虬v ) c g ，( ，) ，( 心。p ) ) 中不存在( 矾v ) ? 路，则缈，砂中至少有一条边不属于 e ( g ) ，否则“，v 虬( y ) ，与假设矛盾我们分两种情况来讨论： a ) 有一条边不属于e ( g ) ，不妨设砂芒e ( g ) ，则“n ( x ) ，因为 ( 心( y ) ) 连通，薪以在( g ( ) ，) ) 中存在( x ，v ) 路p ，。矗是 ( 蠢( ，) ) 中的( v ) 一路，矛盾 b ) 若砂ge ( g ) ，v y 甚e ( g ) ，则，v ，y n ( x ) ，对x 局部完全化 “v e ( q ) ，矛盾 综上所述，( q ( y ) ) 连通- 在证明引理2 2 之前，我们首先引进下面的记号：对x 矿( g ) ，x 非局部连 通，设只= ( “，v ) i “，v e g ( x ) ，( e ) ) 中不存在( ”，- 路 ；记g “，恐，) 为在g 中对一，x ：，t 进行局部完全化后所得的图，其中而，屯，x ，属于v ( g ) 引理2 2 若g 是无爪连通图，若z v ( g ) ，且x 非局部连通，j ( “，v ) 疋使得 g x 中存在( “，v ) 路p ，矿( p ) 中至多包含v ( g ) 中两个非局部连通的点，则 可( g ) 是完全图 证明 我们用反证法来证明假设d ( g ) 非完全图，则存在砂叠e ( d ( g ) ) ， x ，y 矿( g ) ，因为g 是连通的，在g 中存在( x ，y ) 一路p ，设尸= “，x ：x ， 一类无爪| 冬| 的几个性质 若v k ( p ) ，置在f ，( g ) 中局部连通，则冈d ( g ) 是g 的闭包，所以x l 在c i ( g ) 中的邻域是团，我们。，得x y e ( c ，( g ) ) ，与假设矛盾，所以至少存在一点 t r ( e ) ，工，在c ，( g ) 中非局部连通，要证明引理2 2 ，我们只需证明置在c t ( g ) 中局部连通下证x ，在d ( g ) 中局部连通若在g 中局部连通，由引理2 1 知 薯在c ，( g ) 中局部连通 若x 在g 中非局部连通，由引理2 2 的假设，j ( “，v ) s x 使得g t 中存 在( “，v ) 路鼻，矿( 只) 中至多包含下面只证矿( 只) 中有两个非局部连通点时，x ，局部连通，有个非局部连通点时同理可证 设( 虬v ) 是使得只= m ：心“，v 为满足条件的最短的路且”g ( 五) ，下面分 三种情况来分析 情形1 “，v 非局部连通，则对u i 进行局部完全化后，“：g u 。) ，对“：进 行局部完全化后，u u ，g u ，“： ，对“，进行局部完全化后， u v g ”。，心，珥) = g 7 ，t 在g 中的邻域为h ) ，五在g 中的邻域为两个不 交且不连边的团，因为( “，v ) 最，所以“，v 属于不同的团，( 心，( 一) ) 可由在 ( 。 ) ) 中加边“v 后得到，所以( 。，n ) 漶连通的，由引理2 i ，一在d ( g ) 中 是局部连通的 情形2 甜，v 非局部连通，“2 ， 对“进行局部完全化后，u 的邻域的生成子图是一个团，则x 。包含u 的邻域 在g 0 ) 中也是一个团 对进行局部完全化后，( 。( “) u 。( ) ) 是一个团，则t 包含“的邻域在 g 红，“ 中也是一个团继续这样下去， 对“。进行局部完全化后，( g ( “) u g ( 砘) u u 。( u , - i ) ) 是个团：则t 包 含“的邻域在g 玑“。鹄) 中也是一个团 类无爪图的几个性质 对q + 一进行局部完全化后，q “m g “，“l q 。珥+ 继续这样下去， 对，进行局部完全化后，1 1 1 1 ；g “，“v 以_ ”m + r 以) 在g 7 = g u ，“l 鹄。，q 中， ( t ) = g ) u ( g ( “) 、b ) ) u g ( ) u u g ( u l - i ) ，置在g ，中的邻域可由 两个顶点不交的团覆盖，一个包含“，一个包含v ，因为“，v g ，所以这两个 团连通由引理2 1 ，x i 召f c l ( g ) 中是局部连通的 情形3 “，巩非局部连通，虬，芒 口，v ，k 1 2 ， 对“进行局部完全化后，“的邻域的生成子图是一个团，则置包含“的邻域 在- g u ) 中是一个团 。 对“进行局部完全化后，( 似) u 名( m ) ) 是一个团，则包含“的邻域在 g u ，“。 中也是一个团继续这样下去， 对“。进行局部完全化后，( ，j ) u ，g ( m ) u u ，g ( 蚱。) ) 是一个团；则x ， 包含“的邻域在g p ，嵋一。) 中也是一个团 对u l + l 进行局部完全化后，l l l u l + 2 g 虬“r 。i f , + 。) 继续这稗下去， 。 对u k - i 进行局部完全化后，q g “，“l 鹄- ，珥+ ，钆一0 = g 7 对v 进行局部完全化后，v 的邻域的生成子图是一个团，则x 包含v 的邻域在 g v ) 中也是一个团 对“，进行局部完全化后，( ：( v ) u ( 坼) ) 是一个团，则置包含v 的邻域在 g 7v ，u t ) 中也是一个团继续这样下去， 对“。进行局部完全化后，( j ( v ) u 心( 蚱) u u r g ( 蚝+ 。) ) 是一个团，则t 包含v 的邻域在g 7 v ，虬，- u k + 。) 中也是一个团 在g ”= g ， v ，u t 以+ i ) 中， 9 一类无爪隆| 的几个性质 。，在g 。中的邻域可 由两个顶点不交的团覆盖，一个包含u ，一个包含v ，且因为，虬g 。，所以这 两个团连通由引理2 1 ，t 在c ，( g ) 中是局部连通的一 定理2 1 的证明“；”情形1 若y ( g 1 ) n 矿( g 2 ) a ，v x 矿( g 】) n 矿( g ) ， 则屯( x ) 2 ，噍( x ) 2 ( 否则与m ( g ) 控制集矛盾) ，由已知得g 中存在满足条件 的圈c 使得c 上至多有3 个非局部连通的点，若y y ( g ) ，且y 非局部连通 ( ( y ) ) 有两个不交且不连通的团，设为。，2 ，“矿( 1 ) ，v 矿( 2 ) ，若( ) ) 的两个团属于同一g ，显然g 一y 中存在( “，v ) 一路暑，矿( 鼻) 上最多有两个非局 部连通的点若y 的两个团属于不同的g ，则令y 在m 。中由u 控制，y 在坞中 由v 控匍j ( 或y 在g 2 中的邻点为v ，v 在鸩中由控制) ，因为c 上最多肴3 个非局 部连通的点，不妨设有3 个，c = f x i x 2 。t 2 y i 乃其中f ，是非局部连通的 点，一y ( m ) ，一矿( 鸩) ：m 。中存在( “，一) 一路只，m ：中( v ，) 一踌最( 或 ( ，y ，) 一路足) ，则勰x ，f ，：最v ( “p i x i f y ，是y o v ) 是g y 的一条( 虬v ) 一路p ， 矿( p ) 中最多有两个非局部连通的点由引理2 2 ，d ( g ) 是完全图+ 情形2 矿( g i ) n 矿( g 2 ) = a ，由已知得g 中存在满足条件的圈c ，使得c 上有 4 个非局部连通的点，且至少存在一个非局部连通点x ，使得 毛0 ) 之2 ，电( x ) 2 ，设x g 。，因为矿( g 1 ) n 矿( g 2 ) = o ，所以z g 2 又因为 ( z ) 22 ，设“，v y 口x ：- f f g ：中的邻点，则，v 为g 中非局部连通的点，否则与 矿( g 1 ) n 矿( g 2 ) = a 矛盾，且w ( g ) 否则与g 是无爪图矛盾设“由y o 控制， v 由y ，控制，且与v 不属于“的同一个团，即y o ve ( g ) ，否则矾e ( g ) 。与 y ( g 1 ) n 矿( g 2 ) = 彩矛盾，则膨：中存在( ，乃) 路p ，则砂。e y 。是g 2 一“中的一条 ( v ，) 路只，y ( 露) 中有一个非局部连通的点，由引理2 2 ，对矿( 弓) 中的局部连 o 、lj “i 一 坼 ，u m u 、ijk h u l lo ，l 、j卜心，l u 、j t ，l m 1 1 )一(m 一类无爪图的几个性质 通点进行局部完全化后，i , l 为局部连通的点，记此时所得图为g ，则 x 矿( q ) n 矿( g ) ，由情形1 ，c ，( g ) 是完全图 “仁”假设g 不满足g 中存在连接这两个分支的圈c ，使得c 上存在非局部连 通点x ，使得屯( x ) 2 2 ，屯( x ) 2 ，其中q2 ( 矿( m ) u ( m ) ) ，但c ，( g ) 是完 全图，则g 是哈密顿的，g 中存在连接m ，m ：的圈c 。c 上非局部连通点的邻 域或完全属于g ，或如图z 所示，局部完全化后，c ，( g 1 ) ，c ，( g 2 ) 为完全图，x 非局 部连通，所以d ( g ) 不是完全图，矛盾 定理2 2 的证明充分性：( 1 ) ；d ( g ) 是完全图：由引理2 2 可得因为x 矿( g ) ，且x 非局部连通，oo ) 由两个不交且不连通的团覆盖，设为n i ，n 2 ，设“m ，v m 若 “，v g ，显然在g i x 中存在连接虬y 的路p ，v ( p ) 中至多有两个非局部连通的点； 若“g ，v e q ( f ，) ，由已知存在连接鸩，m 2 ，蝎的圈c ，c 上有三个非局部连通 钓点，设c - t ：x 2 x 。, t 2 y y 2 y 。，3 z i z2 z 。，其中x 。m | 。y j m2 z f m3 t l 是非 局部连通的点；不妨设e g z ，v e q ，工由”控制，v 由_ 控制或v 肘( g ) ，则 p = 越只”v ，v 或尸= 妃乃v 是g x 中连接“，v 的路，矿( p ) 中至多有两 个非局部连通的点其中p f 是m ，中的路分别连接“，x 。和v ，y ，或v ，y ， ( 2 ) jc ，( g ) 是完全图：由定理2 1 知，c ，( ( 矿( 吒) u 矿( 瓯) ) ) 是完全图，记此时所得 图为g 7 ，则m ( g ) 有两个分支，由已知存在连接这两个分支的圈c ，c 上存在点x 使得吱，( 叩。唧 ( x ) 2 ，屯( x ) 2 ，满足定理2 l 的条件，所以“( g ) = “( g ) 是完 全图 一类无爪阁的几个性质 必要性：假设g 不满足条件( 1 ) 、( 2 ) ，但d ( g ) 是完全图，则g 或为不存在m ，m ，使 得( 矿( p ，) u 矿( q ，) ) 满足定理2 】的条件且不满足( 1 ) ，此时f ，( g ) 由三个连通的完 全图组成，或存在m ，m 。使得( 矿( g ，) u 矿( 吒) ) 满足定理2 1 的条件但不满足存 在连接m ，m ，与m ，的圈c ，c 上存在非局部连通点工使得 t ，嘛( ，) ( z ) 2 2 ，屯( x ) 2 ，由定理2 1 的证明可知，此时c ，( g ) 由两个连通的完 全图组成，与d ( g ) 是完全图矛盾所以g 必满足条件( 1 ) 或( 2 ) 推论的证明要证c f ( g ) 是完全图，我们对r 进行数学归纳法 r = 1 ，2 时，由定理9 和定理2 1 知，d ( g ) 是完全图我们假设( m ( g ) ) 的分 支个数小于r 时成立，下证( 肘( g ) ) 的分支个数等于，时成立令g ，c g ， ( m ( 0 7 ) ) 包含( m ( g ) ) 的r 一1 个分支；由归纳假设，d ( g 7 ) 是完全图，此时所得 图为g ，不妨设m ，匹g ，因为m ，与m ，( i = l 2 ，r - i ) 使得( y ( e ) u 矿( g ) ) 满 足定理2 1 的条件，此时m ( g 。) 有两个分支且g 。满足定理2 i 的条件，所以 ， c z ( g ) = c t ( g ”) 是完全图 f 喵考虑更一股的情况： g 是无爪连通图，肘( g ) = x x e y ( g ) ，x 局部连通) 是g 的一个控制集， ( m ( g ) ) 有r 个分支，设为m ，肘，哆，若c ，( g ) 是完全图，则对g 可进行下列操 作： 存在材，m ：使得( 矿( g ，) u 矿( g ：) ) 满足定理2 1 的条件或膨，掰，使得 ( 矿( g ，) u 矿( q ) u 矿( g ) ) 满足定理2 2 的条件，由定理2 1 和定理2 2 知 c ，( ( 矿( g ，) u 矿( q ) ) ) 和d ( ( 矿( g ，) u 矿( q ) u 矿( g j ) ) ) 为完全图，记这个局 部完全化后的子图为k 7 ， 选择托( 或吖。) 使得( 矿( g ) u 矿( k “) ) ( 或缈( g 。) u 矿( 置“) ) ) 满足 一类无爪斟的几个性质 定理2 1的条件或选择鸩，m 。( 或吖。，鸩) 使得 ( 矿( g ) u 矿( q ) u 矿( k “) ) ( 或( 矿( g 。) u 矿( g j ) u 矿( 足“) ) ) 满足定理2 2 的条件，记此时局部完全化后的子图为x 7 继续下去，直到不能找到满足条件的 矿，设此时所得图为g 1 对g 1 进行如上的操作，一直下去，直到g 满足定理2 1 或定理2 2 的条件 否则若在进行如上操作到g 7 时不能继续下去，且g ，不满足定理2 1 或定理2 2 的条件，则d ( g ) 不是完全图 一类无爪l 芏| 的几个性质 第三章一类无爪图的泛圉性 3 1 、引言 由定理1 6 知对任意k 2 ，存在k 连通无爪图g ，g 不是泛圈的，但d ( g ) 是 泛豳的在 3 5 1 0 0 提出了下面的的问题和猜想，本章主要对这个问题和猜想做了一 些探讨本章讨论的图的阶至少为3 问题确定最大数气( 珂) ，勺( 胛) 为g 中不包含长为f ( 3 s i 阼) 的圈，这些i 的个 数，其中fz ( a ) f = ”，g 是无爪连通图且“( g ) 是完全图 猜想令c i ，c 2 为固定的常数，n 充分大，则对任意阶为n 的无爪图g 且d ( g ) 是完 全图，都包含所有长为i 的圈，其中3 f s q ，? l - - c 2 i h 3 2 、主要结果及其证明 1 主要定理及其证明 定理3 1 若g 是无爪连通图，m ( g ) = x i x v ( o ) ，x 局部连通) 是g 的一个控 制集，( 肘( g ) ) 有两个分支，设为m ，m ：，若d ( g ) 是完全图，则g 是泛圈的 证明设g i = 妒( m - ) u ( m - ) ) ，q = ( v ( m 2 ) w n ( m 2 ) ) ，f g j f ：m ， f g ：i = ”：g 。，g 2 是无爪连通图且m ( g 1 ) = x l x 矿( g ) ，x 局部连通 i m ( g ：) = x j x v ( a ：) ，x 局部连通) 分别是g 。，g ：的连通控制集( 由g 。，g ：的定 义，吖( g 1 ) ，吖( g 2 ) 是存在的) 由定理1 8 ，g ，g ：是泛圈的，e 【g i 中存在圈e ， 3 f 玛，g ：中存在圈c ，3 i r 6 ，则g 中存在圈c 。，3 i s _ m a x n ，啦 由定 理1 7 知要证g 是泛圈的只需证g 中存在连接m 。，m 2 的圈c ， cs m a x , r i ，n 2 + l ，下证这样的圈是存在的 情形l 矿( g 1 ) n 矿( g 2 ) a ，f 龟i r u ，v ( g , ) r 、v ( g 2 ) ，v i 矿( g 1 ) ，v 2 矿( g 2 ) ， v i v 2 e ( g ) 或h = v 2 矿( g ) n 矿( g 2 ) ，“。h ，q 吃 一类无爪| 璺i 的几个性质 因为g l 是泛圈的，所以g - 中存在( u ) 一路只= 砘一毛y ，i 鼻l l j 因为g 2 是泛圈的，所以g ：中存在( ，v 2 ) 一路最= v z y l y ：y , u ， 我们假设矿( 日) n 矿( ) 一 m ，h ，v 2 = a ，则令c = “。只v , v z 足“， 阱 c i s l j + l 等j + - 否则若矿) n 矿( 最) 一“，h ，屹) a ，则令0 是矿( 暑) 中 使得气= 乃最小的的指标，我们可选取v l = v 2 ，令c 7 = “，只气最h ， c 怄h + k + l 忆下面假设m ) 州聃以) 观 若矿) n m o ，则c 即是所要求的圈下证这样的尸是存在的 若不存在，即i p i阱 但矿( p ) n m = a ，：不妨设矿( 只) n 肘，= a ，若 e f i j 一，设只= “m 以v 。，s l j z ，因为“在g 。中的邻域是团，设“ 在6 。中由x 1 6 。m ( g ) ) 控制，则一“：e ( o ) ， ， 令鼻：= u t x i “2 “，q ， 只k 阱t 小阱滞足黼劂牡阱 若”。为偶数，u i 在g ；中邻域为团，d ( g 1 ) 是完全图，由定理1 5 知c l ( g , - - 1 1 1 ) 也是完全图，在g 一“。中存在b ，v 1 ) 路p ，| p i _ n , - 2 ，令只= “，x 。n 。，则 1 只l 生手+ 1 = n _ 2 l ，满足条件，矛盾，所以为奇数；i 鼻1 = 兰若g ，中 包含g 中的堕一1 个局部连通点时，“由五h m ( g ) ) 控制，v ，由 x 2 ( x ：em ( g ) ) 控制，因为m 一连通，所以存在( 而，屯) 一路p ，lp i 鱼一2 ，令 p = u l x , a ：v 一，| 只| n , 2 - 1 - 2 + 2 = 堕，p 靴a g , 中至少包含g 中的堕个 一类无爪恻的几个性质 局部连通点，若至少包含_ n i - - 1 + 1 个时，则鼻中至少有一个点是g 中的局部连通 点，矛盾；f s f i v a g ，中包含g 中的丁n i - 1 个局部连通点，且g 是泛圈的，设 c = 1 a i l l t t u y l x , x 2 - l 为g f 中的m 圈，u j , v l 是g 中的非局部连通点，x ，是g 中 的局部连通点，医a # s l p , i = 丁n i - l ，所以地“，g e ( 6 ) ，3 ，地hg ( g ) ， “- e ( g ) ，f 2 ( 否则令只l l l x t q ，f 只j 下n t - - 1 ) ，所以吨( “，) = 2 ， 一薯+ tge ( g ) ，2 ( 否则令鼻= “ x 。x ：。川，鼻【堕) 且五+ t 芒e ( g ) ， 。j2 ( 否则令只_ m i x l g i i + k u 2 + k v i ，i e i 童丁n t - 1 ) ，同理x t v t te ( g ) ，又茵“在g 。 中的邻域是团，所以充k ) = 3 ，“) = u i , ：，x 2 ) ，v 2 x l + tg e ( g ) ，k - 2 ( 否则 令尸； i “2 x l + k 毛。“，l 鼻l _ n i r - - 1 ) ，所以如( “：) 4 ，因为一局部连通，x ：与 “，：之一相邻，“恐叠皇( g ) ，所以恐“：e ( g ) ，“：在g 中是非局部连通点，则 u 2 在g l 中的邻域或是一个团，或是两个团，若是一个团时，则 “，e ( g ) ，x i 毪e ( g ) ，矛盾；所以“：在g l 中的邻域是两个团，因为如( “：) 4 e 1 - i 在q 中的邻域是团，所以心) = u i , 码，_ ，叠) ，且因为( u i ，x 1 ，屯) 连通，所 以“，而e ( g ) ，矛盾( 其中v ，可能与蚝柏同) 综上所述，这样的路是存在的 情形2矿( g i ) n 矿( g ：) = a ，且c 上存在非局部连通点“。，使得 屯( m ) 2 ，屯( 地) 2 2 ，不妨设“t 由m t 控制“t 在g 中的邻域是团，由情形1 的证明知，g 中存在( “z ) 一路只( 心在g 2 中有邻点q ) ，使得i 鼻j 【j 且 y ( 只) n m o 设。在g ：中的邻点为 1 1 ，。：，硝。) ，m 22 一类无爪图的几个性质 断言m ：是g ： “。：，铂。) 的连通控制集，且v x m ：，x 在g z u 。甜l ，) 中 是局部连通的 证明 “，在g ：中的邻域是团( 否则与g 是无爪图矛盾) 且“，：，这些点在 g 中为非局部连通点( 否则与矿( g 1 ) n 矿( g 2 ) = o 矛盾) ，所以m ：是g ：、 m ：，川，) 的连通控制集下证m ：，x 在g ： “。：，, 4 ，。) 中是局部连通的 g ： n 1 2 , - “。) 是连通无爪图( 因为m ：是g ：的连通控制集) ，要证 v x em ：，x 在g ：“：，。) 中是局部连通的，即i a t _ ( ：，扛) ) 连通，其中 g 7 = g ：、 ：，“。) 因为v u 。，它们不可以由同一个局部连通点控制( 否则 与矿( g 1 ) n 矿( g 2 ) = a 或“。“。，非局部连通矛盾) 若( ( x ) ) = ( ，( x ) ) ，显然x 在g 7 中局部连通若( g ，( 。) ) = ( 。( x ) “，) ，当( ( x ) ) 连通且连通度大于等于 2 时，( g ，( x ) ) = ( ，：( x ) 弘，) 也连通若连通度为i ，则( ( x ) ) 可由两个顶点 不交的团覆盖使得连接这两个团的边在其中一个