关于图是可迹或1—哈密尔顿的两个充分条件

设G是一个图，G的独立集Y称为本质集，如果存在[y1,y2}属于Y，使得dist（y1,y2）＝2。利用插点方法，给出了关于（k-1）或(k 1)－连通（k≥2）图G是可迹的或1－哈密尔顿的统一证明。     

平面三角剖分图的L(2,1)标号

图G的L（2，1）标号是从一个顶点集V（G）到非负整数集的函数f(x)，使得若d(x,y)＝１，则|f(x)-f(y)|≥２；若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。本文证明了对最大度数为△的一般平面三角剖分图G，有λ（G）≤△^2-△；当G的直径大于2时，有λ（G）≤△^2-△。     

一类极大临界h连通图的性质

设G是h连通图，图G的顶点υ称为临办点，G－υ不再h连通，如果G的每个顶点都是临界的，则称G为临界h边连通图。对于G中任意两个相邻的项点x与y，G＋xy不再临界h连通，则称G为极大临界h连通图。引入图的粘合的概念，讨论了δ（G）＝3h／2－1的极大临界h连通图的性质，得到了这类图有关原子，最小点割和分支的重要性质，这有利于进一步研究这类图的结构。     

二分图中度条件与[a,b]-覆盖图

设G是一个图,用V(G)和E(G)表示它的顶点集和边集,并设g和f是定义在V(G)上的两个整数值函数且g相似文献   

一个不等式的推广

文[1]利用一组不等式给出并且证明了如下不等式：设且，本文给出了（1）的一般形式，并由此导出了（1）式及一些有趣的不等式。定理1设当且仅当X；一X。—…一八时取等号。证明1设八x）一e”．显然人工）为凸函数．由Jensen不等式知，y6R，a。＞0（i—l，2，…，。），且7a。一1，有八】a。。。）＜】a。八。。）即eD。。。－〔】a，e。。’－l】－11－l，一个人一In（l－十二），（1。二一1，i一1．2…·．n），将人代入上面09不等式并整理便得（2）式。证明2构造人1）。。l，l（＋x）（x＞－1），则人x）为凹函数。仿照证一的方法可证…     

二分图中相互独立的圈

证明了下面的结论：设k≥1是一个整数，G＝（V1,V2；E）是一个二分图，满足|V1|=|V2|=n≥2k 1。若对G中任意两个不相邻的面点x∈V1，y∈V2，都有d(x) d(y)≥2k 2，并且δ（G）≥2，则G包含k个相互独立的图。     

与任意图2-正交的(g,f)-因子分解

设G是一个图，用V(G）和E(G）表示它的顶点集和边集，并设g(x）和f(x）是定义在V(G）上的两个整数值函数，且对每个x∈V(G），有4≤g(x)≤f(x)，则图G的一个支撑子图F称为G的一个（g，f）-因子，如果对每个x∈V(G)，有g(x)≤dF(x)≤f(x)。图G的（g，f）-因子分解是指E(G）能划分成边不交的（g，f）-因子，设F={F1,F2,…,Fm}和H分别是图G的因子分解和子图，若对所有1≤i≤m有|E(H)∩E(Fi）|=2，则称F和H2-正交。本文证明：若G是一个（mg m-1，mf-m 1）-图，H是G中任一有2m条边的子图，则G有一个（g，f）-因子分解与H2-正交。     

Hamilton图的一个注记

本文的主要结果是：设G是D－圈图,若存在某个t≤δ,使得对任何t＋1个点的独立集,X＝｛x0,x1,…,xz）,有,则G是Hamilton图。     

P2n的边幻和标号算法及超边幻和标号算法

设L为简单无向图G从V（G） ∪E（G）→{1,2,…,｜V（G） ∪E（G）｜}的一个双射函数,若L满足以下条件：对L所有的边xy∈E（G）,x、y∈ V（G）,都有L（x）＋L（y）＋L（xy）=C,C为常数,则L是图G的边幻和标号,图G是边幻和图;若在此基础上,图G的顶点标号满足：L（V（G））={1,2,…,｜X（G）｜},则L为图G的超边幻和标号,图G是超边幻和图;主要研究一类图P2n的边幻和标号以及超边幻和标号,并给出了相应的证明.     

关于n-格图及相关图的L(2,1)标号问题

图G的L(2，1)标号是一个从顶点集V(G)到非负整数集的函数?（x），使得若d(x，y)=1，则|?（x）-?(y)|≥2；若d(x，y)=2，则|?（x）-?(y)|≥1。移动通讯频率分配问题可转化为图的L(2，1)标号问题。将2-格图及相关图推广到n-格图及相关图，并给出了它们的L(2，1)标号。     

关于图存在[a,b]-因子的邻域并条件的注记

设G是一个阶为n的图,a,b,k为正整数且1≤a〈b,2≤k≤[b／a],δ（G）为G的顶点的最小度．若δ（G）≥a,n≥（a＋b）（k（a＋b）-2）/b,且对V（G）的任意独立子集{x1,x2,…,xk}有｜NG（x1）∪NG（x2）∪…∪NG（xk）｜≥an／（a＋b）,则G存在[a,b]-因子．     

关于图的路色数

本文证明了P_∞-K-临界图的一些简单性质,并给出了某些图类的路色数。主要证明了:(1)若x(G,P_∞)=K,则G包含一个P_∞-l-临界子图,这里对所有的l≤K;(2)设G是P_∞-K-临界图,H是G的子图,且H∈P_∞。,则x(G—H,P_∞)=K-1;(3)设T为m阶树,C_n为偶圈,则x(T×C_n,P_∞)=2;(4)若C_n为奇圈,则对任意树T,有x(T×C_n,P_∞)≤3;(5)若m≠n,则x(K_m×K_n,P_∞)=max{[(m 1)/2],[(n 1)/2]}。     

6-连通图最长圈上的可收缩边

 图的可收缩边与可去边是研究连通图的构造和使用归纳法证明连通图一些性质的有力工具。设G是一个6-连通图,e∈E（G）,若收缩e后得到的图仍是6-连通的,则称e是G的可收缩边。采用树型结构理论进行分类讨论,得到如下结论：① 如果P:x=x1x2…xn=y是6-连通图G的一条最长（x,y）－路,xi xi+1是一条不可收缩边,且S={xi,xi+1,u1,u2,u3,u4}是其对应的6-点割,则G-S的每一个断片至少包含P上的一个点;② 设P:x=x1x2…xn=y是6-连通图G的一条最长（x,y）－路,且G的任意断片的阶都大于2。如果P上任意顶点xi都满足条件d（xi）≥7或者若d（xi）=6则[V（P）]中无3-圈包含它,那么P上至少包含一条可收缩边。在上述结论的基础上,进一步研究了任意断片阶都大于2的6-连通图中最长圈上的可收缩边的分布情况,得到如下新结果：任意断片阶都大于2的6-连通图最长圈上至少有两条可收缩边。     

哈密顿图的邻域交和邻域并条件

记δ和α分别为图G=（V,E）的最小度和独立数,1991年Faudree等人和尹家洪分别得到：“若2连通n阶图G的不相邻的任意两点x、y均有｜N（x）∪N（y）｜≥n-δ,则G是哈密尔顿图”和“若2连通n阶图G的长为2的任意两点x、y均有｜N（x）∪N（y）｜≥n-δ,则G是哈密尔顿图”。这里得到结果：若2连通n阶图G的满足1≤｜N（x）∩N（y）｜≤α-1的不相邻的任两点x、y均有｜N（x）∪N（y）｜≥n-δ,则G是哈密尔顿图。此结果推广Faudree等人和尹家洪的结果。     

均衡二部图中的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-因子。     

若干特殊图的广义字典积的星全染色

设G是具有顶点集y（G）={t0,…,t,1}（n≥2）的图,hn=（Hi）i∈0,1…n-1}是不相交图的序列,其中Hi的顶点集为V（Hi）={（ti,y1）,…,（ti,yx},x≥1.文中用构造染色集的方法,研究得到了若干特殊图的广义字典积G[hn]的星全色数.     

与支配集有关的上可嵌入图

结合图的支配集与其他相关条件,证明了如下结果:(1)设G是无环连通图,如果G中含有一个子图为轮W,且V(W)={x,y1,y2,,yt}(t≥3)为图G的一个支配集,则图G是上可嵌入的.(2)设G是无环连通图,如果G中含有一个子图为完全二部图D=(X,Y;E),且V(D)=X∪Y为图G的一个支配集(其中|X|≥3,|Y|≥4),则图G是上可嵌入的.     

扇与Halin图的一致膨胀图的关联色数

设图G的点集V（G）={v1，v2，…vn}，G的膨胀图R的点集V（FG）=V1UV2U…UVn，且对X∈K，y∈Vj，有xy∈E（FG），当且仅当i=j或ViVj∈E（G）。若对所有的i，满足｜Vi｜=t，则称其为G的一致膨胀图。给出了扇与△≥6的Hahn图的一致膨胀图的关联色数，它们均为该膨胀图的最大度加1。     

关于边控制集的一些结论

令G＝（V，E）是一个图，M是边集E（G）的子集，如果有e∈E（G）／M，e至少与M中一条边相连，则称M为图G的边控制集，进一步，若M是匹配，则称M为图G独立边控制集，本文给出关于边控制集的一些结论。（1）设图H，S是两中连勇图，且H,S∈ж，γe(S)=1,M和M′＝｛uv｝分别是图H和S的唯一最小边控制集，其中S是图1中的（G1，G2，G3，G4）四个图之一，对任何点x∈V（S）＝｛u,v｝,y∈V(H)-V(M),令G＝H（y=s)S，则G∈ж，（2）如果连通图G≠K2，G∈ж，γe(G)=k,则存在G的两个连通于图H，S和某两个正整数l,m使H∈ж，S∈ж，且γe(H)=k-l,γe(S)=l,G≌H（yi=xi)S,其中l≤i≤m.     

树和K2,n的膨胀图的关联着色

设图G的点集V（G）=（v1,v2…,vn）,Vi是点集（i=1,2,…,n）,G的膨胀图FG的点集V（FG）=V1∪V2…∪Vn,且对x∈Vi,y∈Vj有xy∈E（FG）,当且仅当i=j或vivj∈E（G）．若对所有的i,满足｜Vi｜=t,则称其为G的一致膨胀图．证明了树的膨胀图的关联色数是最大度加1,K2,n的一致膨胀图的关联色数为最大度加2．