完全二部有向图的迭代线图的泛偶圈性（英文）

泛圈性是网络拓扑结构(图或有向图)的一个重要拓扑性质,也是度量网络性能优劣的一个重要指标。LCBD(d,n)是一类稠密的二部有向图,它是完全二部有向图K_(d,d)的(n-1)重迭代线图。本文研究了LCBD(d,n)的泛偶圈性,通过LCBD(d,n-1)的Euler回构造了一个2d^n位的序列,证明了LCBD(d,n)是泛偶圈的,并且当n是偶数时,LCBD(d,n)是点n泛偶圈的,当n是奇数时,是点(n+1)泛偶圈的。

一类偶图的顶点——[6,2n]泛偶圈性

一个阶数为2n的偶图G中每个顶点均有长为2k(l≤k≤m)的圈通过,则称G是顶点——[2l,2m]泛偶圈的。作者在文献[3]中证明了如下结果: 设G=(X,Y,E)是一个2n阶连通偶图。如果G中任意一对距离为3的顶点的次数之和不小于n+1,则G中有长为4,6,8,……,2n的圈。除非G是长为6的圈。本文从连通性出发,证明了满足上述条件的图G是顶点——[6,2n]泛偶圈的。深化了上述结果。

一类新的泛偶圈图

一个2n阶偶图G,如果有长为2R(2≤R≤n)的圈,则称其为泛偶圈。本文证明了如下结果:设G=(X,Y,E)是一个2n阶连通偶图。如果G中任意一对距离为3的顶点的次数之和不小于n+1,则G是泛偶圈的,除非是长为6的圈。

二连通二部图的偶泛圈性

范更华证明了如下结论:设G是具有n个点的二连通图(n≥3),若对任一对使d(u,v)=2的点有max{d(u),v(v)}≥π/2,则G是哈密顿圈的。将范氏条件限制在二部图上,已经得到二连通的二部图是哈密顿圈的一个类似充分条件。本文证明该充分条件亦保证了二部图的偶泛圈性:设二连通的平衡二部图G=(X,Y;E)每部有n个点,若对任一对使d(U,v)=2的点有max{d(u),d(v)}>π/2,则G为偶泛圈的。该结果是最好的可能。

二维“格子笼”图的顺序偶泛圈性

给出了顺序偶泛圈图的定义,对二维"格子笼"图的顺序偶泛圈性进行了研究,得到了判定二维"格子笼"图是顺序偶泛圈图的充分必要条件。

关于唯一r-偶泛圈图(英文)

设r≥4且r是偶整数．阶为2n的偶图G被称为唯一r-偶泛圈图，如果对每个偶整数t，r≤t≤2n，G恰含一个长为t的圈，且G不含长小于，的圈．若G是唯一r-偶泛圈圈，则称G是r-UB-图．证明了恰好存在6个外可平面的r-UB-图和对m≤3恰好存在12个阶为2n和边数为2n＋m的r－UB－图．

顺序偶泛圈图的最少边数及其性质研究

研究构成顺序偶泛圈图的边数,得到顺序偶泛圈图的最少边数,同时研究了最少边数的顺序偶泛圈图的性质,得到了最少边数的顺序偶泛圈图是二部图的结论。

唯一偶泛圈图的一个定理(英文)

设 G是一个偶图 ,v是偶数且是 G的阶 .若对每个偶数 t,4≤ t≤ v,G恰有一个长为 t的圈 ,则称G是唯一偶泛圈图 (简称 UB-图 ) .作者证明恰有 6个 v +4条边的 UB-图 .

点泛圈偶图

设Ｇ是连通偶图，（Ｘ１，Ｘ２）是其顶点的二分类，｜Ｘ１｜＝｜Ｘ２｜＝ｎ，δ（Ｇ）≥ｔ≥３，且对于Ｘｉ中的任意两点ｕ和ｖ，均有｜Ｎ（ｕ）∪Ｎ（ｖ）｜≥ｎ－（ｔ－２），ｉ＝１，２，文中对ｔ≤６的情况。

点泛圈偶图的一个充分条件

设Ｇ是连通偶图，（Ｘ１，Ｘ２）是其顶点的二分类，｜Ｘ１｜＝｜Ｘ２｜＝ｎ，δ（Ｇ）≥ｔ≥３。证明了若任意ｕ，ｖ∈Ｘｉ蕴含｜Ｎ（ｕ）∪Ｎ（ｖ）｜≥ｎ－（ｔ－２），ｉ＝１，２，则当ｔ＝７时Ｇ是点泛圈偶图。

邻域并与点泛圈偶图

设Ｇ是连通偶图，（Ｘ１，Ｘ２）是其顶点的二分类，｜Ｘ１｜＝｜Ｘ２｜＝ｎ，δ（Ｇ）≥ｔ≥３．证明了若任意ｕ，ｖ∈Ｘｉ｜Ｎ（ｕ）Ｎ（Ｖ）｜≥，ｉ＝１，２，则Ｇ是点泛圈图．

邻域并与点泛圈偶图

设G是连通偶图，（X1，X2）是其顶点的二分类，|X1|=|X2|=n,δ（G）≥t≥3。文中证明了：若任意u,v∈X，蕴含|N(u)∪N(v)| ≥n-[(t-1)/2],i=1,2，则G是偶点泛圈。

点泛圈偶图的又一个充分条件

设G是连通偶图，（X1，X2）是其顶点的二分类，｜X1｜＝｜X2｜＝n，δ（G）≥t≥3。证明了若任意u，v∈Xi蕴含｜N（u）∪N（v）｜＞n－（t－2），i＝1，2，则当t＝8时G是点泛圈偶图。

关于r-(P_0,…,P_(t-1))—泛圈图

若G中长为r+tj+i的圈恰好有Pi(0≤i≤t-1)个,其中r+tj+t-1≤n,j是P_0,…,P_(t-1)重复的次数,则称G为r-(P_0,…,P_(t-1))-泛圈图.主要采用构造法,给出当t=8时r-(P_0,…,P_7)-泛圈图的一些结果 .即设n≥14,≥6若2-3+-3≤n<2-2+-2且n-(r_((n,)-1))=s(mod8),s=0,1,…,7时,那么存在一个n阶r-(4,4,4,4,5,5,5,5)泛圈图,其中r=r_(0, λ)+s=﹛2^(λ-4)+3+s,当n≤3·2^(λ-4)+2时n-2^(λ-3)+1+s当n>3·2^(λ-4)+2时同时,利用类似的方法证明了r-(1,1,3,3,4,4,5,5)—泛圈图、r-(4,4,4,4,5,5,5,5)—奇(偶)泛圈图以及r-(1,1,3,3,4,4,5,5)奇(偶)泛圈图.进一步,给出相应圈长分布的最小可能边数.

一类r-(d_(0),d_(1),…,d_(t-1))-泛圈图的结果

设r,t,j是正整数,若对每一个r+tj+i(r+tj+i≤n),n阶简单图G中长为r+tj+i的圈恰好有d_(i)个,0≤i≤t-1,其中t是d_(i)的周期数,j是t重复的次数,则称图G为r-(d_(0),…,d_(t-1))-泛圈图.主要讨论了r-(6·2^(μ_(1)),6·2^(μ_(1)),8·2^(μ_(1)),6·2^(μ_(1)))-泛圈图,r-(6·2^(μ_(1)),8·2^(μ_(1)),6·2^(μ_(1)),6·2^(μ_(1)))-奇(偶)泛圈图.

与泛圈图有关的一些结果

设r,t,j是正整数,对于n阶哈密顿图G,若对每一个r+tj+i(r+tj+i≤n),G中长为r+i+j的圈恰好有di个,0≤i≤t-1,其中t是di的周期,j是t重复的次数,则称图G为r-(d0,…,dt-1)-泛圈图.本文讨论了r-(3,3,4,3,4,3,3,3)-泛圈图,r-(3,5,5,3)-奇(偶)泛圈图,以及g(0,0,6,…,6)的界.

修正冒泡排序网络的边偶泛圈性

对于一个二部图G,如果在G中存在任意长为偶数l(4≤l≤|V(G)|)的圈,则称这个二部图G是偶泛圈的:如果对G中任意一边e,在G中存在任意长为偶数l(4≤l≤|V(G)|)且包含e的圈,则称这个二部图G是边偶泛圈的.修正冒泡排序网络是互连网络中的一个重要的Cayley图模型.在此,证明了对任意的自然数n,当n≥3时,修正冒泡排序网络Y_n是偶泛圈的,同时也是边偶泛圈的.