n-因子-临界图的一个充分条件

证明了如下结论:设G是p阶连通图,其中P≡n(mod2)且n相似文献   

1—坚韧Hamilton图的充分条件

设n≥3阶1—坚韧图,若对于G中任意导出爪K(1．3)或变爪K(1．3)＋e上的三点u,v,w,且d（u,v）＝d（u,w）＝2,均满足｜N（u）∩N（v）｜≥-α－1或｜N（u）∩N（w）｜≥α－1,则G是Hamilton图。     

赋权图中最重的最长v-路与赋权周长

对2－连通非Hamilton赋权图G,本文证明：若P（u,v)是G中最重的最长路，则G的赋权周长C^w(G)≥d^w(u) d^w(v)，假设G满足文中描述的额外条件C1，C2，则max｛d^w(x),d^w(y)|d(x,y)=2｝≥m/2时，对每个顶点v,G含量最重长v-路P（u,v)使d^w(u)≥m/2，而d^w(x) d^w(y) d^w(z)≥m（当d(x,y,z)=2)时，c^w(G)≥2m/3.改进了非赋权图的周长及赋权图的赋权周长的若干已有结果。     

可扩图的一些性质

设G是一个连通的简单图且具有完美匹配。如果G的任一基数为n(n≤(|V(G)|-2)/2的匹配都能扩充为G的一个完美匹配，则称G为n-可扩的。对于S包含于V(G),记M是G[S]的基数为r的最大匹配，并令T＝S－V（M）。对连通的非二部的n-可扩图G（n≥2），得到以下结果：（1）若r≤n且|T|≥2，则|V(G)|≥2(n r |T|--1)。（2）若r≤n-2且|T|≥2，则|V(G)|≥2(n r |T|)。（3）若|V(G)|≤4n-2，则对于任一u∈V(G),G[Г(u)]都有一个基数为n的匹配。     

连通图的临界性

通过连通图的研究给出μ－临界m-连通m－正则图的一种构造方法。并给出关于μ－临界图的结论：G是4－连通（p,q)图，P≥9，如果存在线x=uv及S包含于V（G）使G－x-S有两个支A，B，u∈A，v∈B，则当|A| ≥3或|B|≥3时，G不是μ－临界图。     

关于2—连通图哈密顿路的Lindquester猜测

本文证明了Lindquester猜测:设G是顶点数为n的2-连通图,如果对于G中任一对顶点u,v,距离d(u,v)=2|N(u)U N(v)|≥(n-1)/2,则G有哈密顿路。     

更好的新的充分条件和hamiltonian

引入新的充分条件，即n阶图G的长为2的任两点u和v及与它们均不相邻的任一点w,|N(u)∪N(v)| d(w)≥n，并研究得到其hamiltonian结果为，若2连通n阶图G的距离是2的任意点u、v及与这两点均不相邻的任一点w,|N(u)∪N(v)| d(w)≥n，则G是Hamiltonian图。该文也得到另一个充分条件NC2的进一步的Hamiltonian结果。     

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

设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是点泛圈偶图。     

Hamiltion图的一个充分条件

证明如下结果：G是简单图满足条件：对G中任一对不相邻顶点u、v有max{d(u),d(v)} ｜N(u)∪N(v）｜≥n-1；且对任意T包含V（G），有ω（G\)≤｜T｜，则G是Hamilton图。     

一类图中D—闭迹存在的充分条件

设G是一个简单图,(?)e∈E(G),定义e=uv的度d(e)=d(u)+d(v),其中d(u)和d(v)分别为u和v的度。本文的主要结果是:设G是n≥3阶几乎无桥的简单连通图,且G≠K_(1(?)n-1),G不含C_3和C_4,若对任何三个相互点不交的边e_0,e_1和e_2,d(e_0)+d(e_1)+d(e_2)≥n+7,则G有一个D-闭迹,从而G的线图L(G)是哈密顿图。     

F[Kt]-残差图

利用图的合成运算找到了一种从已知的残差图构造新的残差图的方法；讨论了F—残差图与F[Kt]—残差图之间的某些内在联系，发现了一类新的典型的m—Kn—残差图．     

完全图Kn和完全多部图Kn(t)的{C3,S4}-强制分解

本文给出完全图Kn和完全多部图Kn(t)存在{C3, S4}-强制分解的充分必要条件.     

盒子中蛇问题回溯算法

研究了盒子中的蛇问题,即求ｎ方体Ｑ＾ｎ中最大导出环Ｓｎ问题;已知｜Ｓ２｜＝４,｜Ｓ３｜＝６,｜Ｓ４｜＝８,｜Ｓ５｜＝１４,｜Ｓ６｜＝２６,通过回溯算法证明了｜Ｓ７｜＝４８,｜Ｓ８｜≥９４,并给出猜想｜Ｓｎ｜≤２｜Ｓｎ－１｜－２（ｎ≥３）。该猜想对３≤ｎ≤７已成立。     

完全图K_n分解成五个顶点的星和圈

讨论了完全图Kn分解成五个顶点的星和圈的存在性,给出完全图Kn存在{S5,C5}-强制分解的充要条件是n≥9.以及完全图Kn存在{S5,C5}-分解的充要条件是n≥5(n≠6,7).     

图C~2_n的优美性

给出了图C2n的定义,并对其优美标号进行研究,得到了当n=4k(k≥2)时图C2n是优美图的结论。     

一类图(C)2n的优美性

给出了图(C)2n的定义,并对其优美标号进行研究,得到了当n=4k+1(k≥1)时,图(C)2n是优美图的结论.     

完全三部图K_（n_1,n_2,n_3）的竞赛数

对于一个图G,一般情况下计算它的竞赛数k（G）是很困难的。本文给出了关于完全三部图Kn1,n2,n3（n1≥n2≥n3≥2）的边团覆盖数和竞赛数：θe（Kn1,n2,n3）=n1n2 k（Kn1,n2,n3）={n1n2-n1-n2-n3＋4 n1≥n2=n3 n1n2-n1-n2-n3＋3 n1≥n2〉n3     

关于图Cn1,n2,n3,n4及Cp,q,s的邻接谱

图的谱确定问题是图论中的一个重要问题,它是根据已知的特征值去确定图形,一般说来这是一件很困难的事.图论界的许多学者研究了一些特殊情形,主要涉及图的邻接谱(或图的Laplacian谱)的研究,其研究的一般途径是通过图的邻接矩阵(或Laplacian矩阵)表示,建立图的拓扑结构(特别是图的各种不变量).通过矩阵论,以及组合矩阵论中的经典结论,用于图的拓扑结构的研究.在已有文献的基础上研究了Cn1,n2,n3,n4图和Cp,q,s图的邻接谱问题,得到了不同构的Cn1,n2,n3,n4图及Cp,q,s图没有相同的邻接谱这个结论.     

完全四部图Kn,n,n,n（n为奇数）的竞赛数

本文中,我们给出了关于完全四部图Kn,n,n,n（n为奇数）的竞赛敷的一些结论： k（Kn,n,n,n）{=1,当n=1时,=4,当n=3时,=n^2-4n＋8,当n=2m＋3（m=1,2,…）时     

完全图Kn的{ P4, S4,C4 }-分解

讨论完全图Kn分解成4个顶点的路、星和圈的存在性．给出完全图Kn存在{C4,S4},{P4,C4),{P4,S4},{P4,S4,C4}-分解以及强制分解的充要条件．