爪心独立图中有Hamilton—路的一个充分条件

证明了下面的结论：设Ｇ是（ｋ－１）－连通爪心独立图，若对于每个Ｚ∈Ｉｋ＋１（Ｇ），在Ｇ中有∑／ｘ∈ｚｄ（ｚ）≥（Ｚ）＋ｋ，则Ｇ中含Ｈａｍｉｌｔｏｎ－路。     

爪与圈可扩性

图Ｇ中一个与Ｋ１，３同构的导出子图叫做Ｇ的一个爪，爪中的３度顶点叫它的爪心。用ｒ（ｖ）表示图Ｇ中所有以顶点ｖ为爪心的不同爪的数目。证明了阶数≥３的连通、局部连通图Ｇ，如果Ｇ的爪心集合Ａ是点独立集，且Ａ↓ｖ∈Ａ，ｒ（ｖ）≤ｄ（ｖ）－３，则Ｇ是完全圈可扩的。     

爪心独立图的模k泛圈性

证明了2-连通的爪心独立图G，如果对任意的非爪心点v，有d（v）≥k＋l，对任意的爪心点u，存在v∈N（u），使得d（u）≥忌＋2，那么G是模k点泛圈的．     

无爪图周长的一个下界

本文主要证明了下面两个结论：（一）设Ｇ是３－连通无爪图，若存在顶点ｘ∈ｖ（Ｇ）使，则Ｇ是Ｈ－图。（二）设Ｃ是ｎ阶尽连通无爪图（ｋ≥２），则ｃ的周长ｃ（Ｇ）≥。     

2—连通无爪图的最长圈

本文引入了图Ｇ的幅度ζ（Ｇ）的概念，讨论了２－连通无爪图的最长圈。设ｃ（Ｇ）图Ｇ的最长圈，对于一个非Ｈａｍｉｔｏｎ２－连通无爪图Ｇ，证明了，如果ζ（Ｇ）〈１／２λ（Ｇ），则ｃ（Ｇ）≥２／３ｐ＋１＋２。     

3—连通无爪图的Hamilton—连通性

设Ｇ是ｎ阶３－连通无爪图，δ是其最小次，若ｎ≤４δ－８，则Ｇ是Ｈａｍｉｌｔｏｎ连图。     

（k＋1）——连通无爪图的Hamilton——连通性

一个图若不含与Ｋ１．３同构的导出子图,则称它为无爪图,本文利用Ｔ－插点方法,得到（ｋ＋１）－连通无爪图是Ｈａｍｉｌｔｏｎ－连通的两个充分条件,（１）设Ｇ是（ｋ＋１）－连通无爪图（ｋ≥２）,若对每个Ｘ∈Ｉｋ＋１（Ｇ）有ｓ２（Ｘ）〉１,则是Ｇ是Ｈａｍｉｌｔｏｎ－连通图,（２）设Ｇ是（ｋ＋１）－连通无爪图（ｋ≥２）,若对每个Ｘ∈Ｉｋ＋１（Ｇ）,有∑ｘ∈ｘｄ（ｘ）≥ｎ（ｘ）－ｋ＋１,则Ｇ是Ｈａｍｉｌｔｏｎ     

2-连通无爪图的最长圈

讨论了２－连通无爪图中的最长圈,得到了：当Ｇ是一个非Ｈａｍｉｌｔｏｎ的２－连通的无爪图,且ξ（Ｇ）≥１２λ（Ｇ）时,则ｃ（Ｇ）≥２ξ（Ｇ）＋４．     

一类无爪图的Hamilton圈

设ｖ是图Ｇ＝（Ｖ，Ｅ）的顶点，若存在顶点ｕ∈Ｖ－｛ｖ｝，使子图Ｇ［Ｎ（ｖ）∪｛ｕ｝中任意一对顶点的距离不超过３，则称ｖ是Ｇ的弱局部连通顶，点。设Ｇ是非平凡的连通无爪图，且它的任一顶点割均钫含一个弱局部连通顶点，则Ｇ包含Ｈａｍｉｌｔｏｎ圈。     

4连通无爪图的最大圈长的一个下界

设Ｇ为ｎ阶４连通无爪图，σ５＝ｍｉｎ，则ｃ（Ｇ）≥ｍｉｎ（ｎ，σ５－７）。     

关于Faudree定理的一个注记

假定Ｇ是顶点数的ｎ的２－连通图，Ｇ中顶点数为４且包含爪Ｋ１．３的子图称为爪型子图。本文证明了对Ｇ的任一爪型图Ｆ，任何ｕ，ｖ属于Ｖ（Ｆ），由距离ｄ（ｕ，ｖ）＝２＝│Ｎ（ｕ）ＵＮ（ｖ）│≥２ｎ－１／３，则Ｇ是哈密顿图。     

距离无爪图的Hamilton性

距离无爪图类属于无爪图类。所谓距离无爪图是对图中的每一个顶点,其距离为的邻域的独立数均不超过3的图.F.BruceShephed已证明:若G是距离无爪图且G是2─连通的,则G有Hamilton路;若G是距离无爪图且G是3─连通的,则G有Hamilton圈.本文在此基础上,定义了一种新的禁用子图──网全爪,首先证明了2-连通的、无网的距离无爪图有Hamilton圈.又证明了2-连通的有网、无网全爪的距离无爪图有Hamilton圈.     

无爪图中具有指定长度的路因子

在无爪图G中,设σ2(G)表示不相邻顶点度和的最小值. 令|V(G)|=n=∑ki=1ai,ai6,1ik,并且σ2(G)n+k-1,证明了对于图G中任意的k个顶点v1,v2,…vk, 都存在点不相交的路P1,P2,…Pk，使得对于1ik，都有|V(Pi)|=ai并且vi是路Pi的一个端点.     

平方根图

设G是一个简单图及顶点为u1，u2，…，uv，d(vi)是点vi的度，令^～d(G)={[d(u1)]的平方根，[d(u2)]的平方根，…，[d(uv)]的平方根}，称G是一个平方根图，如果^～d(G)是G的邻接矩阵的一个特征向量，猜想：一个连通图G是一个平方根图的充分必要条件是G是一个正则图或半正则图，这个猜想在本文中得到了证明。     

可平面图3可选择的一个充分条件

给G=(V,E)的每个顶点分配一个色列表L={L(v)|v∈V},若G有一个正常顶点染色φ,使得对每个顶点v∈V,都有φ(v)∈L(v),则称G是L可染的。若对G的每一个满足|L(v)|≥k,v∈V的L,G都是L可染的,则称G是k可选择的。本文通过权转移方法证明了每个不含4,6,8,10圈的可平面图是3可选择的。     

没有某些圈的平面图的3可选择性

设G=(V,E)是一个图,对G的每一点v给一颜色集L(v).G称为L列表可染的,如果存在G的点染色f满足:f(u)≠f(v),(u,v)∈E(G),且f(u)∈L(u),u∈V(G).G称为k可选择的,对于任何列表L(v)(这里每一个L(v)恰有k个元素)G都是L列表可染的.本文研究了没有某些圈的平面图的可选择性,证明了没有4,5,7,10圈的平面图是3可选择的.     

Ore定理的一个注记

对简单图G=(V,E),Ore定理告诉我们如果对G的每一对不相邻的顶点u,v都有d(u)+d(v)≥|V|,则G有哈密尔顿圈.证明了,若G仅包含一对不相邻的顶点u,v,满足d(u)+d(v)＜|V|,G仍有哈密尔顿圈.     

围长至少为6的曲面图的列表单射染色

图G的一个点染色称为单射染色,如果任何两个有公共邻点的顶点染不同的颜色.一个图G称为单射k-可选择的,如果对于顶点V(G)的任何一个大小为k的允许颜色列表L,都存在一个单射染色φ,使得对于v∈V(G),有φ(v)∈L(v).使得G为单射k-可选择的最小k,称为G的列表单射染色数,记作χ_i~l(G).设G是最大度为Δ,围长为g的可嵌入到欧拉示性数χ(Σ)≥0的曲面Σ的一个图.证明了若Δ≥7且g≥6,则χ_i~l(G)≤Δ+3.     

实质矩阵对策的一个充要条件

设A为对策值是v 的矩阵对策G的赢得矩阵 ,a ,b分别是A的最大元素和最小元素 如果A的第i行元素都是a ,那么只要局中人 1坚持用纯策略i,不论局中人 2用何策略 ,局中人 1都将获最好赢得a ,此类“对策”实质上不是真正的对策 ,故称为 1—非实质对策 类似地 ,若A的第j列元素都是b ,则称G为 2—非实质对策 1—非实质和 2—非实质对策统称为非实质对策 ;否则称实质对策 笔者证明了如下结果 :G为 1—非实质对策的充要条件是v =a .G为 2—非实质对策的充要条件是v =b .G为实质对策的充要条件是b 相似文献   

唯一偶泛圈图的一个定理

设G是一个偶图,u是偶数且是G的阶,若对每个偶数t,4≤t≤v,G恰有一个长为t的圈,则称G是唯一偶泛圈图（简称UB－图）。作者证明恰有6个v 4条边的UB－图。