关于Sumner-Blitch猜想的一个注记

设G是一个图。G的最小度，连通度，控制数，独立控制数和独立数分别用δ，k，γ，i和α表示，图G是3－γ-临界的，如果γ=3，而且G增加任一条边所得的图的控制数为2.Sumner和Blitch猜想：任意连通的3－γ临界图满足i=3，本文证明了如果G是使α＝k 1≤δ的连通3－γ-临界图，那么Sumner-Blitch猜想成立。     

图的1-因子、f-因子和(g,f)-因子

设G是一个图且有一个1-因子F,g和f是定义在V（G）上的非负整数值函数且对每个X∈V(G)有g（X）＜f(X)≤dG（x）,且f(v(G))为偶数．（i）若对每个xy∈F有f(x)=f(y)且G－{x,y}有一个（g,f)-因子,则G有一个（g,f)-因子;（ii）若对每个xy∈F有f(X）=f（y）且G-{X,y}有f-因子,则G有f-因子.     

仙人掌图的邻点被扩展和可区别全染色

设G为简单图.G的全k-染色是指k种颜色1,2,…,k对图G的全体顶点及边的一个分配.设c是图G的一个全k-染色,任意的x∈V(G),称■为点x的扩展和,其中N(x)={y∈V(G)|xy∈E(G)}.称图G的全k-染色c为邻点被扩展和可区别(简记为NESD),如果w(x)≠w(y),其中xy∈E(G).使得图G存在NESD全k-染色的最小值k被称为图G的邻点被扩展和可区别全色数,简记为egndi_∑(G).本文利用数学归纳法探讨了仙人掌图的邻点被扩展和可区别全染色,并证明了这类图的邻点被扩展和可区别全色数不超过2.该结论说明Flandrin等人提出的NESDTC猜想对于仙人掌图是成立的.     

极小k边连通图的一个极值问题

本文只讨论单纯图。所有符号的意义均同于[2]。依照[1]给出定义 如图 G=(V,E)具有性质:λ(G)=k,而对(?)e∈E 均有λ(G-e)=k-1,则称 G 为极小 k 边连通图。设已给图 G=(V,E),如果 A,B(?)V,且 A∩B=φ,则记[A,B]={xy↓x∈A,y∈B,xy∈E}。如果 S(?)E,|S|=k,且 G-S=G_1 U G_2 V(G_1)∩V(G_2)=φ,V(G_1)≠φ,     

关于图的L(d,1)-标号问题

图G的L(2,1)-标号是一个从顶点集V(G)到非负整数集的函数f(x),使得若d(x,y)=1,则|f(x)-f(y)|≥2;若d(x,y)=2,则|f(x)-f(y)|≥1.图G的L(2,1)-标号数λ(G)是使得G有max{f(v)v∈V(G)}=k的L(2,1)-标号中的最小数k.Griggs和Yeh猜想对最大度为△的一般图G,有λ(G)≤△2.此文研究了作为L(2,1)-标号问题的推广的L(d,1)-标号问题,并得出了平面三角剖分图、立体四面体剖分图、平面近四边形剖分图的L(d,1)-标号的上界,作为推论证明了对上述几类图该猜想成立.     

二分图中关于Enomoto问题的结果

设k,n1和n2是3个正整数,G=（V1,V2;E）是一个二分图,使得｜V1｜=n1,｜V2｜=n2,其中n1≥2k＋1,n2≥2k＋1并且n1-n2≤1．如果对任意不相邻的x∈V1和y∈V2,都有d（x）＋d（y）≥2k＋2,则G包含k个相互独立的圈．以上结果部分地回答了Enomoto提出的关于二分图有独立圈的问题．     

关于两类平面图及相关图的L(d1,d2)-标号问题

图G的L(2,1)标号是一个从顶点集V(G)到非负整数集的函数f(x),使得若d(x,y)=1,则|f(x)-f(y)|≥(2;若d(x,y)=2,则|f(x)-f(y)|≥1.图G的L(2,1)标号数λ(G)是使得G有max{f(v)V∈V(G)}=k的L(2,1)标号中的最小数k.Griggs和Yeh猜想对最大度为△的一般图G,有λ(G)≤△2.本文将L(2,1)-标号推广到L(d1,d2)-标号,并得出了平面三角剖分图、立体四面体剖分图、平面近四边形剖分图的L(d1,d2)-标号的上界,作为推论,本文证明了对上述几类图,有上述猜想成立.     

极大非独立集可削去的因子临界图

如果对一个简单图G的每一个与G的顶点数同奇偶的独立集I，都有G-I有完美匹配，则称G是独立集可削去的因子临界图．如果图G不是独立集可削去的因子临界图，而对任意两个小相邻的顶点x与y，G xy足独立集可削去的因子临界图，则称G足极大非独立集可削去的因子临界图，本刻画了极大非独立集可削去的因子临界图。     

关于Erdos-Jacobson-Lehel 问题的门槛

设σ(k,n）表示最小的正整数m，使得对于每个n项正可图序列，当其项和至少为m时，有一个实现含k 1个顶点的团作为其子图。Erdos等人猜想：σ(k,n）＝（k-1)(2n-k) 2.Li等人证明了这个猜想对于k≥5，n≥（^k2））＋3是对的，并且提出如下问题：确定最小的整数N（k），使得这个猜想对于n≥N(k）成立。他们同时指出：当k≥5时，[5k-1/2]≤N(k）≤（^k2) 3.Mubayi猜想：当k≥5时，N(k）＝[5k-1/2]。在本文中，我们证明了N（8）＝20，即Mubayi猜想对于k=8是成立的。     

极大γt-临界图

如果对没有孤立点的图G的任何一个不相邻于一次点的点υ,子图G-υ的全控制数小于图G的全控制数,则称G是全控点临界的.这类图又被称为γt-临界的.进一步地,如此一个图的全控制数为k,则称它为k-γt-临界的.该文主要是给出一个满足n=△(G)(γt(G)-1)+1的图类的结构性的证明.     

关于Win猜想的部分结果

<正> 本文假定G=(V,E)是2n个点的简单图,我们用C[U]表示点集U的导出子图,用d(x)表示G中点x的次,d_H(x)表示G的子图H中点x的次.其余符号见[3]. 给定非负整数k,若图G中每一对不相邻的顶点u和ν,都有d(u)+d(ν)≥2n+k,则称G为Ore k-型图.S.Win给出下述猜想: 若G是Ore k-型图,则G有k+2个1-因子.其中k≤2n-4.     

3-连通3-正则图中的可序子集

图G的k元点集X={x1,x2,…,xk}被称为G的k-可序子集,如果X的任意排列都按序排在G的某个圈上.称G是k-可序图,如果G的每一个k元子集都是G的k-可序子集.称G为k-可序Hamilton图,如果X的任意排列都位于G的Hamilton圈上.研究了3-连通3-正则图的可序子集的存在性问题.     

汉米尔顿图泛圈性的奥尔型条件

本文所说的图是简单图,未定义的术语见[1,2].n 阶图 G,n≥3,若有长为 n 的圈,则说 G 是汉米尔顿图;若对每个 k,3≤k≤n,G 含有长为 k 的圈,则说 G 是泛圈图.定理1.在 n 阶图 G 中,若对任何点对 x,y∈V(G),xy(?)E(G),都有 d(x)+d(y)≥n,则 G 是汉米尔顿图.     

关于图是(r,n)-临界图的一个邻域条件

设n，m和r是满足r≥2，n≥0，m≥3的整数，且当r是奇数时，假设r≥m-1．称一个图为K1,m-free，如果它不包含以Kt,m为导出的子图．称一个图G为一个（r,n）-临界图，如果在删去G的任意n个点后，剩下G的子图都有一个r-因子,设G是一个Kl,m-free的（n＋1）-连通图，且阶为｜G｜以及r（｜G｜≥n）是偶数,证明了：如果G的最小度至少是r＋n＋m-1，阶｜G｜≥8r5＋n，并且对V（G）的任意独立点集{x1，x2}都有｜NG（x1）∪NG（x2）｜≥（｜G｜＋n）／2，那么G是一个（r,n）-临界图．关于G的最小度和｜NG（x1）∪NG（X2）｜的下界是紧的。     

关于P_n~3的优美性(英文)

设G(V,E)是一个简单图,对自然数k,当V(G~k)=V(G,E(G~k)=E(G)∪{uv|d(u,v)=k},则称图G~k为k-次方图,本文证明了图P_n~3的优美性。     

P_n~k的均匀全染色

设G(V,E)是一个简单图,f是G的一个k-正常全染色,若f满足||Vi∪Ei|-|Vj∪Ej||≤1(i≠j),其中Vi∪Ei={v|f(v)=i}∪{e|f(e)=i},则称f为G的k-均匀全染色,简记为k-ETC.并称eχT(G)=min{k|G存在k-均匀全染色}为G的均匀全染色数.本文将通过很好的全染色方法得到eχT(Pkn)=5(n≥2k+1),并证明了对Pkn,[5]中猜想是正确的.     

Pkn的均匀全染色

设G(V,E)是一个简单图,f是G的一个k-正常全染色,若f满足||Vi∪Ei|-|Vj∪Ej||≤1(i≠j),其中Vi∪Ei={v|f(v)=i}∪{e|f(e)=i},则称f为G的k-均匀全染色,简记为k-ETC.并称χeT(G)=min{k|G存在k-均匀全染色}为G的均匀全染色数.本文将通过很好的全染色方法得到χeT(Pkn)=5(n≥2k 1),并证明了对Pkn,[5]中猜想是正确的.     

关于（ξ,k）—临界图

设G为连通图,且ξ（G）=k≥1,若对G中任意边e,均有ξ（G\e）=k-1,则称G为(ξ,k)-临界图。本文刻划了ξ-1-临界图的若干性质,给出了一个图为ξ-1-临界图的一些充分或必要条件,以及一些ξ-1-临界图类。     

二分(mg,mf)-图中的(g,f)-因子

设G是一个二分图具有顶点集V（G）和边集E（G）。设g和f是定义在V（G）上的两个正整值函数使对任意的x∈V（G）有g(x)≤f(x)，G的一个（g,f）－因子H是G的一个生成子图满足g(x)≤dH(x)≤f(x）。若图G本身是一个（g,f）－因子，则称G是一个（g,f）－图。本文得到一个（mg,mf）－图具有特殊性质的（g,f）－因子的充分条件，从而推广了文献[6]中的一个结果。     

有关Euler函数(n)的方程的正整数解

设(n)是Euler函数.主要研究了方程(xy)=3((x)+(y))的可解性问题,利用初等的方法给出了这一方程的所有的35组正整数解.对于任意素数k>3,(x,y)=(3k,4k),(4k,3k)是方程(xy)=k((x)+(y))的2个正整数解.证明了更为一般的结论:对于任意奇数k>3,当gcd(k,3)=1时,(x,y)=(3k,4k),(4k,3k)是方程(xy)=k((x)+(y))的2个正整数解.