完全二部有向图的迭代线图的泛偶圈性

泛圈性是网络拓扑结构（图或有向图）的一个重要拓扑性质,也是度量网络性能优劣的一个重要指标。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）泛偶圈的。     

二连通二部图的偶泛圈性

范更华证明了如下结论:设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-(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≤n2-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当n3·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)奇(偶)泛圈图.进一步,给出相应圈长分布的最小可能边数.     

关于二部图圈的一个注记

设G=（X,Y;E）是连通二部图,│X│= │Y│=n,则（1）NC2=n≥4,则G是点泛圈偶图。（2）NC2≥n-1≥4,且6≥2,则G含有Hamilton圈,或者G的任何一点都含在G中长为2n-2的圈中,且这个圈为G的控制圈。     

给定指数的本原有向图的哈密尔顿性质<英>

本文研究了给定指数n+s(n-2)的本原有向图的哈密尔顿性质,并得到如下结果:(1)设D是围长为s≥2,指数为n+s(n-2)的n阶本原有向图,如果D中有一个r-圈,使降(r,s)=1.则D是哈密尔顿的。(2)设D是包含环,指数为2n-2的n阶本原有向图,则D是哈密尔顿的充要条件是d(D)=n-2,这里d(D)是使γ(n,v)=γ(D)的n到v的最大距离。     

图的谱半径和泛圈性

设G=(V,E)是一个n阶m条边的简单连通图,μ(G)为图的邻接矩阵的最大特征值。本文利用图的谱条件讨论了图的泛圈性,证明了n(n≥5)阶图G,如果μ(G)n-2,则G是泛圈图除非G=Kn-1+e。     

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

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正则有向图是几乎渐进肯定泛圈的。更进一步，给出了一个在这种随机扰动有向图中构造任意长度有向圈的算法。     

对2连通n阶图某些结果的改进

研究 NC≥ n-δ条件下 Cnm 点泛圈图的性质 ,得到 2连通 n(n≥ 6 )阶图 G.若 N C≥ n-δ,则 G是 Cn5 点泛圈图或 Kn/ 2 ,n/ 2 .改进了 Faudree等人的一些结果     

有向图的控制圈

采用有向图控制圈的研究方法对有向图控制圈进行了研究 ,证明了 :设 D为 n阶 ( n≥7)强连通有向简单图 ,且对 D的任意弧 ( x,y)有 d-( x) + d+ ( y) >n- 4,那么 D含有控制圈     

边数q≥C2p-1-1的(p,q)图的泛圈性研究

泛圈图长期以来是图论中研究的重要课题之一,该文利用图的包装理论研究图的泛圈性,得到n阶(p,q)图G当边数q≥C2p-1-1时G为泛圈图的充要条件.     

边数q≥C_(p-1)~2-1的(p,q)图的泛圈性研究

泛圈图长期以来是图论中研究的重要课题之一,该文利用图的包装理论研究图的泛圈性,得到n阶(p,q)图G当边数q≥C2p-1-1时G为泛圈图的充要条件.     

一类新的泛偶圈图

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

一类三圈三色本原有向图指数上界

根据非负本原矩阵簇与其伴随有向图的一一对应关系,研究了一类三圈三色本原有向图,它的未着色图中包含n个顶点,一个n-圈、一个(n-3)-圈和一个2-圈,给出了本原条件和本原指数上界.     

带有极端负惯性指数的图的探讨

设G是一个图,G的邻接矩阵的负特征根的个数叫图G的负惯性指数,记为n(G).证明了n(G)=1当且仅当图G的非孤立点形成一个完全二部图;n(G)=n-1当且仅当图G≌Kn;找到了n(G)=n-2的许多图类G;也找到了n(G)=2的许多图类G;最后提出了一个猜想.     

一个本原有向图D的scrambling指数及广义scrambling指数

对含有4个圈(1个n-2圈,2个n-3圈,1个n-4圈)的n阶本原有向图D的scrambling指数和广义scrambling指数进行研究.通过分析图的特点,结合图论原理并根据本原有向图scrambling指数和广义scrambling指数的定义,利用集合的运算得到了该图的scrambling指数和广义scrambling指数.     

一类含有两个(n-1)-圈的三色有向图本原指数

为研究非负矩阵簇的本原指数问题,将双色有向图推广到三色有向图.利用有向图与矩阵的对应关系,研究了一类三色有向图,它的未着色图中包含n个顶点,一个n-圈和两个(n-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)的界.     

一类特殊双色有向图的指数上界

本文考虑了一类特殊的双色有向图,它的未着色图有4n-1个顶点,包含一个（3n—1）一圈和一个n-圈,给出了本原条件和指数上界,并对极图进行了刻划。     

关于Hamilton图的新的圈结构定理

设G是一个n阶图,若对于每一个k (3≤k≤n),图G都含有k-圈,则称图G为泛圈图.泛圈图是圈理论研究中的重要课题.研究得到了Hamilton圈上两个不相邻的点在圈上的距离是3的泛圈性结果.     

一类恰含三个圈的三色有向图的本原指数

一个三色有向图D是本原的,当且仅当存在非负整数h、k和v, 且h+k+v>0,使得D中的每一对顶点(i,j)都存在从i到j的(h,k,v)途径, 称h+k+v的最小值为D的本原指数。 本文研究一类特殊的三色有向图,其未着色图恰含一个n-圈、一个(n-1)-圈和一个2-圈, 给出了本原条件和本原指数上界, 并对本原指数上界的极图进行了刻划。