随机图G(2n,p)中k-匹配的相变性质

随机图G(n,p)模型中有两个参数n和p,n表示图中的结点数,p表示图中任意两个不同结点之间独立生成边的概率。证明了随机图G(2n,p)中存在k-匹配的临界值为p=kn-2。实验分析了随机图G(2n,p)实例中10-匹配和25-匹配以及k=n-1匹配的相变。最后总结出临界函数与匹配的边数和结点数有关系。实验表明,理论与实验一致。     

Erdos-sos猜想的一个结果

借助图的包装理论,证明了当k=n-3时,Erdos-Sos猜想（如果G是一个有q条边的n阶简单图,并且q〉1/2n（k-1）,则G包含具有k条边的所有树）成立．     

完全三部图K(n-4,n,n)的色唯一性

设G是简单图,用P（G,λ）表示图G的色多项式．若对任意图H使P（H,λ）＝P（G,λ）,都有H与G同构,则称G是色唯一图．用K（m,n,r）表示完全三部图,证明了当K＝4时,如下猜想[1]成立：对非负整数n,k,当n≥k＋2时,K（n－k,n,n）是色唯一图．即当n≥6时,K（n－4,n,n）是色唯一图．     

连通图中圈数

用|V（G）|、|E（G）|和f（G）分别表示图G的顶点数、边数和圈数．设F（k）＝｛f（G）;G是满足|E（G）|－|V（G）|＝k的无环连通图｝,n（k）＝minF（k）和N（k）＝maxF（k）．证明了下述结果：（1）n（k）＝k＋1;（2）N（k）≤2k+1;（3）对每个整数k≥1,N（k）≥2k＋k（k－1）＋1且当1≤k≤4时等式成立;（4）对每个整数k≥1是奇数时,N（k）≥2k3;当k≥2是偶数时,     

正则图的最大-团横贯数与减最大-团横贯数

本文首先得到了阶数为n、团数为k的连通k-正则图的最大-团横贯数的上界n/k以及n阶连通无爪3-正则图的最大-团横贯数的下界n/4,并对达到这些界的极值图进行了刻画。然后对阶数为n、团数为ω（G）的任意图G 的减最大-团横贯数给出了一个紧的下界1＋ω（G）-n,同时对阶数为n、团数为k的连通k-正则图的减最大-团横贯数呈现了一个上界n/k,并刻画了达到这个上界的极值图。     

双外平面图的点染色

图染色问题是图论研究中的重要问题之一,本文针对双外平面图G的点色数进行研究,并证明了：（1）不加剖分点时,当顶点数为6n＋k（n=1,2,…）（k=1,2,3）时,xv=4;否则xv=3.（2）xv=4时,当在相同面上两端的顶点标号冲突时,若剖分点加在这个标号相对的边上时,仍然有xv=4;否则xv=3.     

均衡二部图中的M-2-因子

设G=（x，y）是一个二部图，若｜X＋=｜Y｜，则称G是一个均衡二部图，文章证明了设G是2n阶均衡二部图，对任意正整数k≥2，若n≥4k-3，且最小度δ（G）≥n＋2（k-1）/2，则任给G的一个完美匹配M，G中存在一个包含M的所有边的恰含k个分支的M-2-因子。     

联结数与分数（k，n’）一临界消去图

设G是一个图,若删除G中任意n’个顶点的剩余子图依然是分数k-消去图,则称G为分数（k,n＇）-临界消去图．笔者证明了若k≥2,n,≥0,bind（G）≥^（n＇＋1）且6（G）≥k＋n＇＋1,则G是分数（k,n＇）-临界消去图．     

棒棒糖图的Merrifield-Simmons和Hosoya指数

i（G）表示图G的Merrifield-Simmons指数,定义为图G的独立点集个数;z（G）表示图G的Hosoya指数,m（G,k）表示G的k-匹配数,则z（G）是所有的m（G,k）的总和（1≤k≤[n/2]）,其中n是G的顶点数．给出n阶棒棒糖图Ln．k的Merrifield-Simmons指数和Hosoya指数以及它关Merrifield—Simmons指数和Hosoya指数的一个排序．     

关于S.Win的一个猜想

令G是一个图,P=|V(G)|,(?)u,v∈V(G),uv(?)E(G),d(u)+d(v)≥P+K,其中k是整数,则称G为Ore k—型图。S.Win提出如下猜想:若G是2n(n≥1)阶Ore k—型图(-1≤k≤2n-4),则G具有k+2个边不重的1—因子。本文证明了k=-1时,Win猜想成立。实际上,除个别图处,我们证明了更强的结论:若G是2n(n≥2)阶Ore-1—型图,且G(?)H_i(i=1,2),则G具有两个边不重的1—因子。     

二分图中存在包含经过给定边的大国的2-因子的度条件

该文主要证明了若G=（V1，V2：E）是一个满足｜V1｜=｜V2｜=n≥sk的二分图，其中k,s,n为3个正整数且k≥2,s≥4，如果σ1,1（G）σ2[（1-1/s）n＋k]，那么对G的任意k条独立边e1，…,ek,G有一个包含k个点不交的圈C1,…Ck的2-因子，使得ei∈E（Ci）,且｜Ci｜≥2s.     

关于三部图K(m,n,r)-A(|A|=2)色唯一性的几个结果

设G是简单图，用P（G，λ）表示图G的色多项式．令K（m，n，r）表示完全三部图。G=K（m，n，r）-A（｜A｜=2），3≤m≤n≤r.证明了若图Y使得P（Y，λ），则Y=K（m＋α,n＋β,r-（α＋β））-S，其中α,β是整数，且｜S｜=e=（r-m）α＋（r-n）β-2（α^2＋αβ＋β^2）≥0.且e=2时，G和Y同构，同时给出了α，β的范围。     

2-连通三圈图的零化度

本文所考虑的图均为无向简单图．图G的特征多项式的根称为图G的特征值,也构成图G的谱．图G的谱中零根的个数称为该图的零化度,记为η（G）．设Gn表示所有顶点数为n的图的集合,[0,n]=0,1,2,…,n,非空子集N∈[0,n]．若对A↓k∈N,都E←G∈Gn,使得η（G）=k,则N称为Gn的零化策本文主要研究2-连通三圈图的零化度．     

树图的全控制数

设G为n阶连通图，集合S称为图G的全控制集，如果V（G）的每个顶点都和S中某点相邻。图G的全控制数，记为γt（G），是图G的全控制集的最小基数。证明了对阶数n≥3且T≠K1，n-1的树T，γt（T）=min{（2n/3），n-l，[n/2]＋l-1}，这里l表示树T中叶子的数目。     

Kn—e图中的路因子

G是一个Kn-e图,e∈E（Ka）。设σ2（G）表示不相邻顶点度和的最小值．令｜V（G）｜=n=∑^ki=1 a,并且σ2（G）≥,n＋k-1．证明对于图G中任意的k个顶点v1,v2,…vk。存在点不相交的路P1,P2,…Pk,使得对于1≤i≤k,都有｜V（Pi）｜=ai．并且vi是Pi的一个端点．     

三个5-阶图与圈Cn联图的交叉数Cn

联图G∨H表示将G中每个点与H中的每个点连边得到的图．在Klesc M给出所有3阶图和4阶图与圈Cn联图的交叉数的基础上,利用反证法和排除法确定了G1,G2,G3三个5-阶图与圈Cn联图的交叉数,他们的交叉数分别是cr（G1∨C2）=Z（5,n）＋2[n/2]＋2,cr（G2∨Cn）=Z（5,n）＋2[n/2]＋2,cr（G3∨Cn）=Z（5,n）＋2[n/2]＋3.     

奇星对九阶轮的Ramsey数(英文)

给定两个图G₁和G₂,Ramsey数R（G₁,G₂）是指具有如下性质的最小正整数n:对任意的n阶图G,或者G包含G₁,或者G的补图包含G₂.令S_n表示n阶星,W_m表示m+1阶轮.当n≥6且n是偶数时,人们证明了R（S_n,W₈）=2n+2.本文证明了当n=5,7,9时, R（S_n,W₈）=2n+1.     

有关Hamilton图与连通度的一个充分条件

利用插点方法和H-序列,证明了如果G是n阶简单图,k=k（G）≥k≥2．而（a1,a2,…,ak＋1）是H-序列,若对于任意的Y∈Ik＋1^（e）（G）,有∑i=1^k＋1aisi（Y）＋sk＋1（Y）〉n＋k＋k-3,则G是Hamilton-图,该定理也是对这方面已有的某些定理的有效推广。     

对称群Sn（n≤15）的一个新刻画

本文首先通过计算给出了对称群Sn（n≤15）的阶｜Sn｜,最高阶元的阶k1（Sn）,次高阶元的阶k2（Sn）及第三高阶元的阶k3（Sn）。然后利用有限单群分类定理证明了Sn（n=1,2,…,9,11,13,14）可由｜Sn｜和k1（Sn）刻画,即有限群G同构于Sn当且仅当｜G｜=｜Sn｜且k1（G）=k1（Sn）。最后对Sn（n=10,12,15）证明了它们可由｜Sn｜和k1（Sn）,k2（Sn）及k3（Sn）刻画,即G 同构于Sn当且仅当｜G｜=｜Sn｜且k1（G）=k1（Sn）,k2（G）=k2（Sn）及k3（G）=k3（Sn）。     

图的圈和路剖分

设G是一个顶点数为n的图,k为任意正整数且k≤n．Hikoe Enomoto和李浩证明了：如果一对不相邻顶点的度和至少为n-k 1,其中k≤n，则除了k=2，G=G5,G能被剖分成k个子图Hi，l≤i≤k，其中Hi是圈或K1或K2．本文中证明了任何一对不相邻顶点的度和至少为n-k，则G能被剖分成k个子图Ki,l≤i≤k，其中Hi是圈或是路．