无爪图中圈的弦的最大数目

本文讨论无向简单图。设C=v_1v_2…v_mv_1是图G的一个圈,G的边v_iv_i称为C的一条弦,如果i(?)j±1(其中v_(m+1)=v_1)。我们用σ(C)表示圈C的弦数,σ(G)表示图G中弦的最大数目。     

关于禁用子图与Hamilton性的新结果

不含导出子图同构于K_(1,3)或F的图称{K_(1,3),F}-free图.设图G含有无弦的点控制圈(简称VD-圈):C=C_1C_2…C_kC_1,并假定依下标顺序给定一正向.用C_(ij)表示沿C的正向从C_i到C_j的一段道路.如果{C_i,C_j}是G的2-割集,当G无爪(K_(1,3)-free)时,G-{C_i,C_j}恰有两个分支.用G_(ij)表示G的满足G_(ij)∩C=C_(ij)的极大连通子图.设P=v_0v_1…v_(d-1)v_d是G的一条直径路,X={x∈V|d(x,P)>l}.当G是{K_(1,3),F}-free图且d≥3时,同文献[1]定义     

K_(1,3)-free图中的圈

本文说的是简单图。 设G是任一个n阶的图。如果G中有长为n的圈,则G是哈密顿图。如果对每个k,3≤k≤n,G含有长为k的圈,则说G是泛圈图。如果对G的每个顶点v,图G中都有长为k的圈经过顶点v,则说G是点k圈图。如果对每个k,3≤k≤n,G都是点k圈图,则说G是点泛圈图。     

k-连通无爪图中的Hamilton路和Hamilton-连通性

本文涉及的图都是无向简单图。而无爪图就是不存在顶点的导出子图同构于K_(1,3)的图。 1985年,Matthews等讨论了无爪图中的最长路和最长圈。证明了:设G是一个n阶无爪图,其最小次δ≥1/3(n-2)。若G     

关于圈并的补图的色唯一性

设c_p表示长为p的圈,G1_(?)G_2表示图G_1与G_2的并图,(?)指图G的补图。Farrell和Whitehead猜测:圈的补图(?)(p≥5)是色唯一的。在本文中我们证明了如下的主要定理。 定理 设G是2正则图且不合‘,和‘.为其子图,则G是匹配唯一的当且仅当(?)是色唯一的。     

关于简单MCD图的一个定理

设S_n是n个顶点的没有两个等长圈的简单图的集合。如果对于S_n中的一个图G,S_n中不存在适合|E(G′)|>|E(G)|的图G′,则称其为简单最大圈分布图,简称简单MCD图(ma-     

CP~n的(0,1)热核形式

设G=(V,E)是一个靠阶无向简单图,G称为Hamilton图,如果G含一个圈C使得V(c)=V(G)。     

Hamilton图泛圈性的Ore类条件

在本文中,所有的图都是简单图,未定义的术语是常见的。众所周知,一个n阶图G,若对任何点对x,y;xy(?)E(G)总有d(x)+d(y)≥n,则G是Hamilton图(Ore,1960);进一步,G是泛圈图或二部图~K(n/2),n/2(Bondy,1971年)。     

(a,b,k)-临界图

本文所考虑的图皆指有限无向简单图。设G是一个图,具有顶点集合V(G)和边集合E(G)。文中未加说明的记号和定义参见文献[1]。设S(?)V(G),用G[S]表示G中由S导出的子图。用d_G(x)表示顶点x在G中的次数。设a和b是两个非负整数且a≤b。图G的一个[a,b]-因子是G的一个支撑子图H,使对任意的x∈V(H)有设。如果去掉图G的任意k个顶点所剩的图仍有[a,b]-因子,则称图G是(a,b,c)-临界图,或者说G是(a,b,k)-临界的。如果a=b=n,则简称(a,b,k)-临界图为(n,k)-临界图。如果n=1,则简称(n,k)-临界图为k-临界图。Plummer和Lovasz讨论了2-临界图的特征和性质。于青林给出了k-临界图的特征。刘桂真和于青林研究了(n,k)-临界图的特征。本文考虑a相似文献   

完美匹配树最小正特征值的界

设G为n阶简单图,称其邻接矩阵A(G)的特征值为G的特征值。因A(G)是实对称方阵,故G的特征值均为实数,可按大小顺序排列:λ_1(G)≥λ_2(G)≥…≥λ_n(G)。若G是     

n-可扩图的局部邻域条件娄定俊

设G是阶为v的图且具有完美对集。设n是正整数,满足n≤(v-2)/2.G称为n-可扩的,是说:G中任意n条独立边包含在G的一个完美对集中。 设G是一个图且v∈V(G)。定义N_k(v)={u|u∈V(G)且d(u,v)=k}。设u,v∈V(G)满足d(u,v)=2.记I(u,v)=|N(u)∩N(v)|。定义散度α~*(u,v)如下: n_(u+v)(W)=max{|S||w∈N(u)∩N(v),S是G[{w}∪N_G(w)]中包含u和v的独立集},     

论1坚韧图的周长

设G是一个连通图且t为实数,若对V(G)的每个子集S,tω(G—S)≤|S|,其中ω(G—S)是G—S的分支数,则称G是t坚韧图。显然,1坚韧图是2连通的,图G的周长c(G)是指G的一个最长圈的长度。虽然对2连通图的周长的研究已有若干结果,但对1坚韧图周长的研究尚少。本文只讨论有限、无向、无环及无重边的图,且块均指非平凡块,所用术语及记号同文献[4],主要结果是如下定理。     

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

给定一个图G,以‘(G)表示G的周长,并记一(。卜Mi·{客“(一):‘一,ng一Li的结果:设G是”阶2一连通图,若厅(G))n李3.则G是哈密尔顿图. 推论2设G‘留;,若生(3,一23)2,》15奇数;1一2r|l!|||夕、||||书纷we A\是G的无关集a3(G)(3,一16),》16偶数;·3(。卜Mi·{客己(一卜!愈N(一,!”(14。:,。2,,3}是G的无关集则G是哈密尔顿图. 该推论改进了G〔罗1,若内(G)Fa夕bender的结果:设、。)一Mi·{{(知一14),(,)1一2李|训州日N(,‘:{,,,,2,。丹是G的无关集·、(‘卜Mi·{{立N(一)卜{一提使自N(。)铃价的无关集13),则G是哈密尔顿图. 推论3.设G…     

n阶弦图精确个数及脊梁弦图个数的估计

(i)给出n阶弦图个数的精确公式,(ii)给出n阶脊梁弦图个数的上下限.此上下限表明本文的估计为渐近最佳.此外,得到了n阶Vassiliev纽结不变量的维数的上限,即对任意n≥3,上限为1/2(n-1)!;对于较大的n,上限为(1/2(n-1)!-(1/2(n-2)!.此上限是基于Chmutov和Duzhin之工作,并对其结果(n-1)!有所改进.对于n=3和n=4,1/2(n-1)!是最佳值.     

素数度循环图的同构因子分解

设N={0,1,…,n-1},n且在modn意义下-S=S;即存在r_1,r_2,…,r_k使得。 一个n阶简单图G称为以S为特征集的循环图,如果(ⅰ)V(G)=N,(ⅱ)E(G)={(i,j)|j-i∈S},这里减法运算取modn(以下均同)。R={r_1,r_2,…,r_k}称为G的半特征集。     

一类图集的Ramsey数

在图G的一个顶点v上加一条端线e=vw,w(?)V(G),称为G的一次发芽。由图G分别在它的每个顶点处一次发芽而得到的图集,称为G的一次发芽集,记为(G)_1。图集(?)中所有图的一次发芽集的并集,称为(?)的一次发芽集,记为(?)_1。图G的2次发芽集(G)_2可由(G)_2=((C)_1)_1定义。一般,C的n次发芽集(G)_n可递归地定义为     

圈长唯一的最大图的边数

Erds于1975年提出了下列问题:设f(n)是有n个顶点的任何两个圈的长均不相等的图的最大可能的边数。试确定f(n)。 含有f(n)条边、没有两个等长圈的n个顶点的图称为圈长唯一的最大图。     

具有最多边的唯一因子图

§1.引言 设G=(V,E)是简单图,V和E分别是G的顶点集和边集。n=|V|称为顶点数,m=|E|称为边数。设S(?)V,从G中去掉S得到的子图,用G-S表示,就是V-S生成的子图。 G的两条边e_1,e_2若有一个公共端点,称为是关联的.设F(?)E是G的边子集,F中任     

关于线图的泛圈性

线圈的概念是人所熟知的;记号L(G)表示简单图G的线圈。图G满足什么条件才能使得其线圈L(G)是Hamilton图?进一步,这些条件意味着线圈L(G)是泛圈图吗?这些问题是令人感兴趣的。 下列结果是已有的。 定理(Brualdi和Shanny) 如果G是有n≥4     

二阶椭圆型方程组广义解的 L_φ属性

设G是n维欧氏空间E~n 中的有界区域.设l相似文献