蕴含强哈密尔顿连通性的几个条件

利用收缩技术,推广了有向图理论中哈密尔顿性问题的几个结论,给出了有向图是强哈密尔顿连通的最小半度、度和、最少边数等条件．     

数理科学与化学——哈密尔顿连通图和邻域并条件(Ⅰ)

记G=(V,E)是简单图,δ表示图G的最小度,NC=min{|N(x)∪N(y)|:x,y∈V(G),xy(?)E(G)},NC_2=min{|N(x)∪N(y)|:x,y∈V(G),d(x,y)=2}。1989年Faudree等证明了:若3连通n阶图G,NC≥(2n+1)/3,则G是哈密尔顿连通图。据此进一步研究NC_2≥(2n+1)/3,而且研究到2连通图,得到下面结果:若2连通n阶图G,NC_2≥(2n+1)/3,则G是哈密尔顿连通图或G=φ。     

有向笛卡尔积图的k-限制弧连通度

笛卡尔积图是大型互联网络最重要的数学模型之一.有向图的k-限制弧连通度是弧连通度和限制弧连通度的推广,可用于度量网络的可靠性.强连通有向图D的弧子集S被称为D的一个k-限制弧割,若D-S有一个顶点数至少为k的强连通分支D_1,使得D-V(D_1)包含一个顶点数至少为k的连通子图.若这样的一个弧割存在,则称D是λ~k-连通的.D中最小k-限制弧割所含的弧数称为D的k-限制弧连通度,记做λ~k(D).在有向笛卡尔积图中,推广2-限制弧连通度的结论到k-限制弧连通度,得到有向笛卡尔积图的k-限制弧连通度的上界和3-限制弧连通度的下界,并用例子说明所得界是紧的.     

随机扰动有向图的泛圈性（英文）

Dirac定理指如果n个顶点的图G最小度至少为n/2，则G包含一个哈密尔顿圈. Bohman等引入了随机扰动图模型并证明了对任意正常数α和最小度至少为αn的图H，存在一个仅依赖于α的常数C使得对任意p≥C/n H∪G_n,p是几乎渐进肯定哈密尔顿的。本文考虑了随机扰动有向图模型，证明了对任意α=ω{(logn/n)^1/4}和d∈{1, 2}，一个最小度至少αn的n点有向图和随机d正则有向图是几乎渐进肯定泛圈的。更进一步，给出了一个在这种随机扰动有向图中构造任意长度有向圈的算法。     

λ'最优定向图的最小度条件

图的限制弧连通度是度量网络可靠性的一个重要指标.称强连通有向图D的弧割S是一个限制弧割,若D-S包含一个非平凡的强连通分支D'使得D-V(D')包含至少一条弧.限制弧连通度λ'(D)是指最小限制弧割的弧数.λ'最优有向图是使限制弧连通度尽可能大的一类有向图.定向图是一类重要的有向图.定向图和多部定向图是λ'最优的一些最小度条件将被给出.这些结果推广了Grüter等关于竞赛图的相关结论.     

超级λ′定向图的最小度条件

图的限制弧连通度是度量网络可靠性的一个重要指标.设D是一个强连通有向图,其弧割S是一个限制弧割,若D-S包含一个非平凡的强连通分支D′,使得D-V(D′)包含至少一条弧.限制弧连通度λ′(D)是指最小限制弧割的弧数.一个强连通有向图是超级λ′的,若它的限制弧连通度是极大的且最小限制弧割的数目是极小的.定向图和二部定向图是超级λ′的最小度条件被给出,并用例子说明所给的条件是紧的.     

蕴含强(p,q)哈密尔顿性的几个条件

利用路收缩技术,证明了,如果有向图D满足下列条件中的任何一个,(1)最小半度δ0(D)≥(n+p+q)/2;(2)D是(p+q+1)强连通有向图,且d+(x)+d+(y)+d-(u)+d-(v)≥2(n+p+q)-1,这里,x,y是任意控制顶点对,u,v是任意被控制顶点对;(3)D的弧数超过(n-1)2+q2+p;那么D是强(p,q)哈密尔顿的.     

限制弧连通有向图的充分条件

互联网络常以有向图或无向图作为模型,有向图的限制弧连通性能精确度量网络的容错性和可靠性.称有向图D的一个弧子集S是D的限制弧割,如果D-S中存在一个非平凡的强连通分支D1使得D-V(D1)包含至少一条弧.若强连通的有向图D存在限制弧割,则称D是λ′-连通的.λ′-连通图D的最小限制弧割所含的弧数称为D的限制弧连通度,记λ′(D).设D的围长为g,任取长度为g的有向圈Cg=u1u2…ugu1,令ξ(Cg)=min{(sum from i=1 to g)d+(ui)-g,(sum from i=1 to g)d-(ui)-g}且ξ(D)=min{ξ(Cg)}.本文给出了强连通有向图D是λ′(D)≤ξ(D)的一个充分条件.     

关于有向图的强弧连通度

在图论中,图的连通性研究是一个较重要的方面,因为图的许多性质都与图的连通性有着密切的联系.李慰萱在其所著的《图论》一书中介绍了有向图的各种连通度,并且给出了有关强弧连通度λ_3与最小出入度δ_3的两个结论1.对任何有向图D,K_3≤λ_3≤δ_3.2.若D是一个强有向图,δ_3≥[p/2],则λ_3=δ_3.我们推广了上述第2个结论,得到了下面的结果:定理 若D是一个有P个顶点的有向图,记d_3(v)=min{odv,idv},如果存在整数k(1≤k≤4),使对D中任意k个顶点v_1,…,v_k都有d_3(v_1)+…+d_3(v_k)≥k/2(p-2)+1/2则λ_3=δ_3.     

有向图是极大弧连通的充分条件

设D是一个n阶强连通的有向图.D的逆度定义为,R(D)=∑v∈V(D)max{1/(d+(v)),1/(d-(v))},其中,d+(v)与d-(v)是v的出度和入度.证明了,如果R(D)<2+2/(δ(δ+1))+(n-2δ)/((n-δ-2)(n-δ-1)),其中,δ(D)=min{d+(v),d-(v),v∈V(D)},是最小度,那么,D是极大弧连通的.同时,给出了一个二部图的类似结果.     

二分图中含有大圈的2-因子

设G=(V₁,V₂;E)是一个二分图,其顶点数目满足|V₁|=|V₂|=n≥(k+1)s+1,s和k是满足s≥3并且k≥1的两个正整数. 定义σ_1,1为图G的属于不同分划中的不相邻顶点的最小度和,证明了如果σ_1,1(G)≥2[(1-1/s)n]+2, 则G有一个2-因子包含至少k个圈,使得每个圈的长至少为2s.     

有向图中弧数和回路

本文部分解决了Heydemann等提出的一个猜想。也就是证明了每一阶为n的强连通有向图D,如果最小半次至少为3,至少n~2-6n+21条弧,则D存在长至少n-1的回路。     

图中含有k－因子的一个充分性条件

设ｋ是一不小于３的整数，Ｇ是连通图，具顶点数ｎ≥７ｋ－７，ｋｎ是偶数，且Ｇ的最小度δ（Ｇ）≥ｋ。本文证明了：若对Ｇ中任意一对不相邻的顶点ｕ、ｖ均有２ｎ－１≤ｄ（ｕ）＋ｄ（ｖ）十２｜（ｕ）ＵＮ（Ｖ）Ｄ，则Ｇ有ｋ一因子。     

半无爪图中的路因子

证明了如果G是一个半无爪图且它的最小度不小于d,那么G有一个路因子满足每条路的顶点数不小于d+1。     

Super-Euler迭线图的特征刻划

图中端点度数不是２而内点的度数是２的路叫做枝。文中证明了一个连通图Ｇ的ｎ次迭线图Ｌ＾ｎ（Ｇ）是Ｓｕｐｅｒ－Ｅｕｌｅｒ图的充要条件是Ｇ有一个包含Ｇ的每个度至少为３的项点的子图Ｈ,满足：Ｈ的每个顶点都是偶度;Ｈ的孤立顶点在Ｇ中度至少为３;Ｈ的任何连通分支与Ｈ的其它连通分支在Ｇ中的距离至多是ｎ;对于Ｇ中不在Ｈ中的枝的长度至多为ｎ＋１,对于Ｇ中有端点度为１的枝的长度至多为ｎ。     

关于图的圈和退化圈分拆的一个注记

设G是一个n阶图，k是满足2≤k≤n的正整数，于是得到了如下结论：如果图G的任何一对不相邻的顶点{u,v}，都满足max{dG(u)，dG(v)}≥(n-k 3)／2，则存在k个点不交的子图Hi,使得V(G)=V(H1)∪V(H2)∪…∪(Hk)，其中Hi为一个圈或一个点或一条边．     

几乎2-强二部竞赛图及其得分序列

设Tm,n=(X,Y,E)是一个m×n二部竞赛图,且s(v)表示v在Tm,n中的得分.对于u∈Y,记L(u)={v∈V(Tm,n)|u→v且s(v)=n-1}和J(u)={v∈V(Tm,n)|v→u且s(v)=1}.对于v∈X,L(v)和J(v)的定义是类似的.一个强的二部竞赛图Tm,n称为是几乎2-强的,如果对于每一个x∈V(Tm,n),Tm,n-x-L(x)-J(x)是强的.刻划了蕴含几乎2-强二部得分序列的特征.此结论包含了蕴含2-强二部得分序列的特征.     

图的禁用子图和H—连通性

证明了如下结果：设Ｇ是３—连通图，如果Ｇ满足如下之一：（ｉ）｛Ｋ１，３，Ａ，Ｄ）－ｆｒｅｅ．（ｉｉ）｛Ｋ１，３，Ａ，Ｐ５｝－ｆｒｅｅ．（ｉｉｉ）｛Ｋ１，３，Ｉ｝－ｆｒｅｅ．（ｉｉｉｉ）｛Ｋ１，３，Ｚ３，Ｂ｝－ｆｒｅｅ．则Ｇ是Ｈ－连通的．     

限制度的IC平面图中轻弦4-圈的权和

删去完全图k₄任意一条边所得的图称为弦4-圈. 利用权转移方法讨论限制度的IC-平面图中轻弦4-圈的权和, 证明每个最小度至少为5且最小边度至少为11的IC-平面图含有一个轻弦4-圈v₁v₂v₃v₄v₁, 并证明具有该类限制度的IC-平面图中轻弦4-圈权和的上界小于等于37.     

序约束下单向分类方差分析模型的Bayes变量选择

考虑序约束下单向分类方差分析模型的变量选择问题, 提出两种基于SSVS的Bayes变量选择方法, 并设计一种简单且易操作的Gibbs抽样算法进行后验抽样. 数值模拟和应用实例结果表明, 该方法效果较好.