关于3-可选平面图的一点注记

图G=（V,E）称为L-可染的,如果对给定的列表L={L（v）：v∈V（G））,存在图G的一个正常染色c,满足c（v）∈L（v）．如果对任何｜L（v）｜≥南的列表,图G都是L-可染的,则称图G为k-可选的．本文我们证明了平面图不含4圈,5圈,7圈和三角形距离小于2是3-可选的．     

半径为2的图的hyper-Wiener指标

连通图G的hyper-Wiener指标定义为WW（G）=1/2∑{u,v}∈V（G）（d（u,v）＋d^2（u,v））,其中d（u,v）表示G中u到v的距离.研究了半径为2的树的hyper-Wiener指标,并且给出了计算公式.刻画了阶数n=1＋t＋8/7t^2的半径为2的具有最大hyper-Wiener指标的图,这里t是某些正整数.     

超连通图的充分条件（英文）

设G是一个连通图.图的连通度κ(G)存在一个最小正整数k,使得FV,|F|=k且G-F不连通或是一个平凡图.如果每一个最小点割都孤立G的一个点,则图G是超连通的或超-κ的.定义没有孤立点的图G的逆度为R(G)=∑v∈V1/d(v).得到:设n阶连通图G,最小度为δ,若R(G)1+2/(δ+1)+(n-2δ-1)/((n-1)(n-3)),则G是超-κ的.     

有向图的邻域离散度

作为图的邻域离散度的一种推广,引入有向图的邻域离散度的概念．设D=（V,A）是一个有向图,V的子集S的开邻集和闭邻集分别定义为N^＋＋（S）={u：vu∈A（D）,v∈S}和N^＋[s]=N^＋（S）∪{s},D的一个割策略是V（D）的一个子集S使得N^＋[S]在D中被删除．有向图的邻域离散度定义为S（D）=^max s v{ω（D／s^＋）-│S│,S是D的割策略},这里ω（D／S^＋）：=D-N^＋[S]而ω（D／S^＋）表示有向图D／S^＋的强连通分支数．讨论了有向图的邻域离散度的一些基本性质,研究了Kn和Ks,t的定向图的最小邻域离散度．     

Ⅱ类3-正则图在△-收缩下的一个不变量

设G=（V，E）是一个边色数为4的3-正则图，c：E→{1，2，3，4}是G的一个正常4-边着色．设Ei={（e∈E｜c（e）=i}，D（c）=min{｜Ei｜｜i=1，2，3，4}．记C（G）为G的所有正常4-边着色组成的集合．则定义研（G）=min{o（c）}/c∈C（G）为图G的色特征．证明了m（G）在△-收缩下是一个常数．     

图簇Gj1j2…jt^S^＊（i）（p,tkm）的伴随多项式的因式分解及色性分析

令S1，k表示k＋1个顶点的星，Pm表示m个顶点的路，G是任意的p阶连通图，设V（Pm）={V1，V2，…，Vm-1，Vm}及相应的度序列为（1，2，…，2，1）。S2km＋1^p（i）表示把kPm的每个分支的第i个顶点Vi分别与星S1,k的k个1度点重迭后得到的图，用Gj1j2…ji^S^＊（i）（p，tkm）表示把tSkm＋1^P（i）的每个分支的k度点分别与图G的顶点uj1，uj2，ujt，ujl（t≤p）重迭后得到的图，这里p≥1，k≥2，m≥3，1≤i≤m，t≥1．我们通过讨论图簇Skm＋1^p（i）,U（k-1）K1、S2rm＋1^P（i），S（2r-1）m＋1^P（i）以及Gj1j2…jt^S＊（i）（p，2rmt），Gj1j2……jt^S＊（i）（2r-1）mt）的伴随多项式的因式分解，证明了它们的补图的色等价图的结构定理，推广了张秉儒证明的文[8]中的定理2和定理4。     

关于图的边着色的一个猜想

若G是简单图,v(G)是偶数,χ'(G)=?(G)+1,则存在点v∈V(G),使χ'(G-v)=χ'(G)=?(G)+1.本文对此进行了研究,当图G满足以下条件之一时:(1)设G是含有割边的连通图,χ'(G)=?(G)+1;(2)设G是连通图,κ'(G)=2,G中最多除两个2度顶点外,其它顶点的度数均为k(k2),v(G)=2n+2,χ'(G)=?(G)+1;(3)设图G是k正则图,v(G)=2n+2,χ'(G)=?(G)+1;(4)设图G是有2n+2个顶点的连通图,且除点v的度小于k外,其它顶点的度都等于k,χ'(G)=?(G)+1;(5)设图G是有2n+2个顶点的连通图,且除点u,v,d(v)d(u)k外,其它顶点的度都等于k,χ'(G)=?(G)+1;此猜想也是成立的.     

图的Nordhaus Gaddumm型的代数连通度的界

设图G是n阶的单图,G＇是它的补图．用a（G）表示图G的代数连通度．在很多文献中,已经研究了邻接谱半径的Nordhaus—Gaddum型的界的问题．本文进一步探讨了代数连通度的Nordhaus—Gaddum型的界．得到：对树和其他一些图,a（G）＋a（G＇）≥1成立,并刻画了等式成立时的图的特征．根据这些结果,最后提出这样一个猜想：对n阶的单图G,有n（G）＋n（G＇）≥1.     

2-（y，P，1）设计的可解区传递自同构群

设P是一个奇素数,（G,J）是一个对,这里J是一2-（v,p,1）设计,G是J的一个可解区传递自同构群．如果u〉（p3/4＋1）^p-1,则v是一个素数q的方幂,且G要么旗传递,要么G≤AГL（1,u）．进一步,当n为奇数时,p=q或G是奇阶的．     

2-（v,p,1)设计的可解区传递自同构群

设P是一个奇素数,（G,J）是一个对,这里J是一2-（v,p,1）设计,G是J的一个可解区传递自同构群．如果u〉（p3/4＋1）^p-1,则v是一个素数q的方幂,且G要么旗传递,要么G≤AГL（1,u）．进一步,当n为奇数时,p=q或G是奇阶的．     

复合图点列表着色的可选性

r部完全图Km*r是完全图Kr与空图Sm的复合图Kr[Sm] . Erdo。s P, Rubin A L和Taylor H在[1]提到了确定Kr[Sm]的点列表着色的可选性的问题并证明了ch(Kr[S2]) = r .Kierstead H A[2]证明了ch(Kr[S3]) =[(4r - 1)/3] .假定Gm是圈Cn与空图Sm的复合图Cn[Sm] .考虑了Gm的列表着色的可选性并证明了ch(G2) =3, ch(G3)≤ 4及在n是奇数时, ch(G3) = 4 .     

拉普拉斯整谱三圈图的刻画

如果一个图的拉普拉斯谱都是由整数构成的,那么这个图称为拉普拉斯整谱图。本文首先刻画了拉普拉斯三圈基图中最长圈的圈长c（H）≤6的整谱图,并且找出这些连通的拉普拉斯三圈基图的整谱图;其次刻画了至少含有一个悬挂点的连通三圈图的拉普拉斯整谱图,最后证明了至少含有一个悬挂点的连通三圈图的拉普拉斯整谱图都是由它们的拉普拉斯谱唯一确定的。     

Harary图的外连通度(英文)

一个顶点集是一个Rg-点割,如果它将一个连通图分割成一些连通分支使得每个连通分支至少含有g个顶点.图G的g-外连通度(记作κg(G))是Rg-点割的最小基数.图G的通常的点连通度和上连通度分别相应的为κ0(G)和κ1(G).本文将分别证出第一类和第二类Harary图的κg和刻画它们的Rg-点原子部分.     

关于几类Menger型图

设Ｇ是一个简单图，若分离Ｇ的任一独立集Ｓ的最小点数等于连接Ｓ的点之间的内部不相交路的最大个数，则称Ｇ是Ｍｅｎｇｅｒ型图，本文讨论了几类Ｍｅｎｇｅｒ型图。     

关于连通图最长圈的一个结果

设C是k-连通图G（2≤k≤6）的一个最长圈.H是G-C的一个分支.[5]中证明,若L（H）≥k-2,则｜C｜≥kδ-k（k-2）,这里L（H）表示H中最长路的长度,δ表示G的最小度.本文在H满足特定的条件时,对于k∈{3,4,5}改进了上述｜C｜的度下界.     

无限图的匹配扩张

作为有限图的ｎ－可扩性的一个自然推广，本文引入了ｎ－可扩无限图的概念．我们讨论了ｎ－可扩无限图的若干特性，并证明了无限Ａｂｅｌ群上的连通Ｃａｙｌｅｙ图是２－可扩的当且仅当它不是双向无限路．     

关于图的循环带宽的一些结果

本文给出关于图的循环带宽的一些结果．     

线图的邻域连通度

研究了图G的边邻域连通度λNB（G）和它的线图L（G）的点邻域连通度κNB（L（G））之间的关系,证明了AλB（G）≤κNB（G）．提出了一个新的概念：限制性边邻域连通度λrNB（G）,证明了κNB（L（G））≤λArNB（G）．最后,研究了上述两个不等式成为等式的充分条件．     

Ramsey重数研究

对于图G_1,G_2,2色广义Ramsey数R(G_1,G_2)表示满足下列条件的最小正整数p:如果用2种颜色中的一种对K_p的每一条边染色,总有K_p的一个子图同构于G_i,它的边都染有第i种颜色,1≤i≤2.对K_(R(G))的所有可能的边2-着色中,含有单色子图G的最少的个数称为图G的重数.利用计算机计算了若干不小于5阶图的Ramsey重数精确值:M(C_6)=10,M(P_6)=300,M(P_7)=720;当计算量很大时,利用模拟退火算法得到了若干Ramsey重数的上界:M(B_4)≤51,M(K_(2,4))≤24,M(K_(3,3))≤150,M(K_(2,5))≤47,M(W_6)≤34,M(B_5)≤48.     

一类正则图的边坚韧度

证明了一类r-正则r=x1(G)连通非完全图G的边坚韧度近似等于r/2(1 1/Iv(g)I-2)并且提供了估计一些特殊图类的笛卡儿积和Kroneeker积的边坚韧度的公式.