关于2—连通图哈密顿路的Lindquester猜测

本文证明了Lindquester猜测:设G是顶点数为n的2-连通图,如果对于G中任一对顶点u,v,距离d(u,v)=2|N(u)U N(v)|≥(n-1)/2,则G有哈密顿路。     

连通、局部连通无爪图的2-因子

设G是n阶连通、局部连通无爪图,1)若■v∈V(G),d(v)=2,n≥9,则G有两个分支的2-因子;2)δ(G)≥3,n≥7,则G有两个分支的2-因子.     

泛圈图的一个充分条件

本文证明了:如果G是n(≥9)阶2连通无爪图,且G的每个导出子图Z_1,满足当u,v∈V(G)d_(z_1)(u,v)=2时有|N(u)UN(v)|≥n-3,则G是泛圈图或圈.其中Z_1≌(K_2UK_1)VK_1.     

一类Hamilton图

若P[u,v]是2连通无爪图G的最长路,设dp(xβ,xα)=︱P[xβ,xα]︱-1(xβ相似文献   

图中控制数的有关结论

令G=(V,E)是一个图,点集S V,如果满足N[S]=V(G)(或N(S)=y(G)),则称点集S是一个控制集(或伞控制集).一个连通图G如果满足:对任何不相邻于一次点的v点,G-v的全控制数小于G的全控制数,则称图G是一个γt-临界图.给出连了通无爪3-正则图G的控制数满足γ(G)≤3-n.同时找到一个直径是2的4-γt-临界图.     

邻集并、连通度及最大度和Hamilton连通性

文章讨论了无爪图的Hamilton连通性 ,给出邻集并与最大度的条件下Hamilton连通图的新的充分条件,证明了下述定理 :设G是一个3 -连通简单无爪图 ,连通度为k。如果对于G的每一个k阶独立集S满足 :对 u,v∈S,都有(1)k>3时,│N(u)∪N(v)│≥n-Δ(s) -k +2,(2)k=3时,│N(u)∪N(v)│≥n -Δ(s),则G是Hamilton连通的。     

4等周边连通图的邻域条件

k等周边连通度是一个比边连通度更可靠的网络可靠性参数.连通图G的k等周边连通度定义为γ_k(G)=min{|[X,X]|:X■V(G),|X|≥k,|X|≥k},其中珡X=V(G)\X.令βk(G)=min{|[X,X]|:X■V(G),|X|=k}.图G是γ_k-最优的如果γ_k(G)=βk(G).令G是一个阶至少为8的图.文章证明了如果对于G中任意一对不相邻的顶点u,v,当u和v都不在三角形中时满足N(u)∩N(v)≥3;当u和v中至少有一个在三角形中时满足N(u)∩N(v)≥7,那么G是γ4-最优的.     

不含禁用子图的无爪图的2-因子

讨论了不含禁用子图的无爪图的两个分支的2-因子,主要结论如下:(1)设G是2连通无爪图,且不包含同构于Z1的子图,若G不是圈,则G含有两个分支的2-因子;(2)设G是2连通无爪图,且不包含同构于Z2和H的子图,若G不是圈且|G|足够大,则G含有两个分支的2-因子。     

拟无爪图的性质

讨论了比无爪图更广泛的图——拟无爪图，得到了以下两个结果： (ⅰ)　若图G是拟无爪图，且满足ω(G-S)≤t(G), 则2t(G)=κ(G). (ⅱ) 若图G是拟无爪图，对于任意的控制集D及任意t∈D,至多存在3点u1,u2,u3∈(V-D)满足N(ui)∩D={t}(i=1,2,3), 则γ(G)=i(G)，该结果是最好可能的. 以上结果扩展了无爪图的相应结果.     

一类泛连通的无爪图

本文证明了:如果G是3连通的无爪图且G的每个导出子图A,A~(?)都满足ψ(a_1,a_2)则G是泛连通图(除了当u,v∈V(G),d(u,v)=1时,G中可能不存在(u,v)—k路,k∈(2,3,4)以外)     

拟无爪泛圈图的一个充分条件

设G是一个图.若对G中任意距离为2的点对x,y,总存在u ∈ N(x)∩N(y),使得N[u](C)N[x]∪N[y],则称G是拟无爪图.本文给出了拟无爪图是泛圈图的一个充分条件:设G是n阶2-连通无{K4,P5,A}的拟无爪图,G(≠)Cn,则G是泛圈图.     

Ore-范条件下的k-因子的性质

证明了以下结论.图G是2-连通且含有-因子，如果满足d(u,v)=2→d(u)+d(v)≥n-k,那么图G是1-坚韧的.     

判断k-可序哈密顿-连通图的新条件

具有n个顶点的图G(n≥3)是k-可序哈密顿-连通的(k是整数,且2≤k≤n),如果对于G中每一个具有k个不同顶点的可序集合S={v1v2,…,vk},都存在G中的哈密顿路P包含S且不改变其中元素的次序.本文证明了:对于具有n个顶点的图G,u、v是G中任意两个不相邻的顶点,且d(u)+d(v)≥n+1.如果G是「k+1/2﹁-连通的k-可序图,k是整数且2≤k≤n/12,则G是k-可序哈密顿-连通图.     

无爪图的泛连通性

证明了如果G是3连通无爪图,且G的每个导出子图A、子图T都满足φ（α、α2）,则G是泛连通图（当u、v∈V（G）,d(u,v)=1时;G中可能不存在（u,v）-k路,k=2,3,4除外）。     

完全多部图的符号罗马控制数

设图G=(V,E)是一个简单无向图,若实值函数f:V→{-1,1,2}满足以下两个条件:(i)对于任意v∈V,均有∑_(u∈N[v])f(u)≥1成立;(ii)任意v∈V,若f(v)=-1,则存在一个与v相邻的顶点u∈V,满足f(u)=2,则称该函数为图G的符号罗马控制函数.定义图的符号罗马控制数为γSR(G)=min{f(V)f是图G的符号罗马控制函数}.通过对完全多部图中的顶点数进行分类,给出了当k≥3时,完全多部图K(n_1,…,n_i,…,n_k)的符号罗马控制数的准确值.     

连通、几乎局部连通拟无爪图是完全圈可扩的

G是一个图，B（G）表示G中所有局部不连通的点构成的集合。如果B（G）是独立集，并且对任意v∈B(G),Eu∈V(G),使G[N(v)∪{u}]连通，则称G是几乎局部连通的。如果G中所有爪心构成的集合D（G）是独立集，并且对任意v∈D(G),G[N(v)]是强2－控制的，则称G是拟无爪图。本文证明：连通、几乎局部连通的拟无爪图是完全圈可扩的。     

网格图的2-彩虹控制数

给定一个图G和正整数k,图的彩虹控制函数f是满足下列条件的映射f:V(G)→2{1,2,…,k},使得对某个顶点v满足f(v)=,则∪u∈N(v)f(u)={1,2,…,k},其中V(G)是图G的顶点集,N(v)表示所有与v相邻的顶点的集合.彩虹控制函数f的权定义为w(f)=∑v∈V(G)|f(v)|.图的k-彩虹控制数γrk(G)是所有彩虹控制函数的权中的最小权.研究了2-彩虹控制函数的启发式算法的网格图的构造方法,实验结果表明,基于禁忌搜索策略的模拟退火算法比传统的模拟退火算法具有较好的效果.     

图有H链的一个充分条件

对任意图G,令NC(G)=min|N(u)∪N(v)|,u与v取遍G中一切不邻接的点对.本文证明了NC(G)>(p-2)/2的不含K_3为导出子图的p阶连通图G有Hamilton链.     

关于2连通图的容错直径与宽直径的注记

在实时系统中,容错直径和宽直径是两个度量网络信息传输延迟和性能的重要参数.对于一般的图G,确定它的容错直径Dk困难很大,而确定它的宽直径dk却是个NPC问题,因此讨论它们之间的关系显得很重要.该文讨论了2连通图的容错直径与宽直径之间的一些性质,给出若G是直径为2的2连通图,则d2=D2+1的充要条件为存在两顶点u、v∈V(G),其中uv∈E(G),使得L(G)=L(G;u,v)=4或5.     

极大3等周边连通图的充分条件

k等周边连通度是一个比边连通度更可靠的网络可靠性参数。 连通图G的k等周边连通度定义为γk(G)=min{［X,X-］:XV(G),X≥k,X-≥k},其中X-=V(G)＼X。令βk(G)=min{［X,X-］:XV(G),X=k}。图G是极大k等周边连通的如果γk(G)=βk(G)。令G是一个阶至少为6的连通图。本文证明了如果对于G中任意一对不相邻的顶点u,v,当u和v都不在三角形中时满足N(u)∩N(v)≥2;当u和v中至少有一个在三角形中时满足N(u)∩N(v)≥5,那么G是极大3等周边连通的。