二连通的二部图的最长圈

本文研究的图 G 为简单的无向的二部图.所用术语和符号除说明外皆同[1].c(G)表示 G 的最长圈的长.以(A_1,A_2)为二分类的二部图记为 G(A_1,A_2).(?)=min{d(v)|v∈V(G)}.已有结果:定理1.设 G(A_1,A_2)为二连通的二部图,则 c(G)≥2min{|A_1|,|A_2|,2δ—2}.定理2.设 G(A_1,A_2)为二连通的二部图,且(?)_i=min{d(v)|v∈A_i}(i=1,     

关于定向二部图的得分

我们研究了定向二部图的得分表偶,并且得到了关于非负整数表偶是某个定向二部图的得分表偶的一个刻划。     

平衡二部图的四圈覆盖

对任意的正整数ｋ,如果每部２ｋ个点的平衡二部图Ｇ＝（ｖ１,ｖ２;Ｅ）的最小度大于等于４ｋ／３,那么Ｇ恰好被ｋ个相互独立的四圈覆盖。     

度条件下的二部图的定向图

二部图是具有二分类(X,Y)的简单偶图,其中X的每个顶点与Y的每个顶点相连,若|X|=m,|Y|=n,则这样的图记为K_(m,n).该文研究了K_(n,n)的定向图.对于非负整数a和b,若存在满足每个顶点的入度或者是a或者是b的一个K_(n,n)的定向图,则存在非负整数s和t满足方程s+t=2n和as+bt=n~2.论文证明了如下结论:设s和t是任意两个非负整数,对于满足方程s+t=2n和as+bt=n~2的非负整数a和b,存在K_(n,n)的定向图使得每个顶点的入度或者是a或者是b,从而得到了上述必要条件为K_(n,n)是[a,b]_n可实现的充分条件.     

二部图中的独立6-圈

本文主要证明了对二部图G=(V_1,V_2,E),|V_1|=|V_2|=3k,其中k为正整数.若G的最小度至少为2k-1,则G至少包含k-1个独立6-圈.     

大次和1—坚韧图中的最长圈

给一个图Ｇ，定义σ３（Ｇ）＝ｍｉｎ｛Σ＾３ｉ＝１ｄ（ｖｉ）│｛ｖ１，ｖ２，ｖ３｝｝是Ｇ的无关集｝，ｐ３（Ｇ）＝ｍｉｎ｛│Ｕ＾３ｉ＝１Ｎ（ｖｉ）‖｛ｖ１，ｖ２，ｖ３｝是Ｇ中使│ｎ＾３ｉ＝１Ｎ（ｖｉ）│≠０｝的无关集｝。本文证明了：设Ｇ是ｎ阶１－坚韧图，如果σ３（Ｇ）≥ｎ，则Ｇ包含长度至少为ｍｉｎ｛ｎ，２ｐ３（Ｇ）＋４｝的圈，为个结果推广了若干已知结果，也解决了Ｂｒｏｅｒｓｍａ－Ｈｅｕｖｅｌ－Ｖｅｌｄ     

大次和的1－坚韧图中的最长圈

给一个图Ｇ,定义,是Ｇ的无关集,是Ｇ中使的无关集,本文证明了：设Ｇ是ｎ阶１－坚韧图,如果σｓ３≥ｎ。,则Ｇ包含长度至少为ｍｉｎ的圈。这个结果推广了若干已知结果,也解决了Ｂｒｏｅｒｓｍａ－Ｈｅｕｖｅｌ－Ｖｅｌｄｍａｎ所提猜想的一个特例．     

Hamilton非二部图的弱泛圈性

图G称为弱泛圈图是指G包含了每个长为t(g(V)≤l≤c(G))的圈,其中g(G),c(v)分别是G的围长与周长.1997年Brandt提出以下猜想:边数大于[n2/4]-n 5的n阶非二部图为弱泛圈图.1999年Bollobas和Thomason证明了边数不小于[n2/4]-n 59的n阶非二部图为弱泛圈图.作者证明了如下结论:设G是n阶Hamilton非二部图,若G的边数不小于[n2/4]-n 12,则G为弱泛圈图.     

2—连通正则二部图的长圈

Dirac 定理指出:若 G 是 n 个顶点的2-连通图,(?){d(x)}≥k,则 G 有长至少为 min(2k,n)的圈(见[1]).‖本文把 Dirac 定理应用到2-连通正则二部图,得到如下的结果:定理1 设 G 是2-连通 k-正则二部图,G 的顶点数为 n,则 G 有长至少为 min(4k,n)的圈(k≥2).‖     

二部图含圈和对集的一个结果的证明

证明了对于二部图G=(V1,V2; E),|V1|=|V2|=n,如果满足δ(G)≥([1/2n])+1,则图G有一个生成子图,该子图包含指定长度的圈C和对集M,其中V(C)∩ V(M)=(空集).