双外平面图的全染色

双外平面图是一个平面图,它可以嵌入到平面上并使得它的顶点出现在两个面的边界上。设G是一个双外平面图,V（G）,E（G）,F（G）分别为双外平面图G的点集,边集和面集。G的全色数XT（G）是使得V（G）UE（G）中的任意两个相邻或相关联的元素间均染不同颜色的最少颜色数。本文证明了对最大度为6的双外平面图,全色数是△（G）＋1,其中△（G）为G的最大度数。     

不含3-圈和4-圈的平面图的线性2-荫度

线性森林是所有分支都为路的图,图G的线性荫度la（G）也就是把图的边集分解为互不相交的线性森林的最少数量k.设G为不含3-圈和4-圈的平面图,则la2（G）≤[（Δ（G）＋1）/2]＋2.     

在两个圈的直积图上的平衡二元映射

对于直积图G=Cm□Cn,f：V（G）→Z2={0,1}是任意一个定义在顶点集上的二元映射,定义110=f1（0）,V1=f1（1）。若│┃V1┃-V0┃-┃│≤1,则称映射,是平衡的。f可以自然诱导出一个定义在边集E（G）上的二元映射以：E（G）→Z2,且fE（xy）=f（x）＋f（y）。令E0=fE1（0）,E1=fE-1（1）,那么D（G,f）=┃E1（f）┃-┃E0（f）┃。文章通过在两个圈的直积图Cm□Cn上构造一系列平衡二元映射的方法,完全确定了在平衡映射下的边差集D（Cm□Gn）。     

图的顶点划分与图的上可嵌入性

图G的顶点W-划分是指G的一个顶点划分{V1,V2,…,Vs},其中G[Vi]有生成子图轮W｜Vi｜（1≤i≤s）结合图的顶点W--划分以及顶点度条件,得到了一类新的上可嵌入图类,推广了已有相关结果．     

不含3-圈和4-圈的平面图的线性2-荫度

线性森林是所有分支都为路的图,图G的线性荫度la(G)也就是把图的边集分解为互不相交的线性森林的最少数量k.设G为不合3-圈和4-圈的平面图,则la2(G)≤[△(G)+1/2]+2.     

边色临界图的1-因子和几乎1-因子的存在性

根据Vizing邻接引理和关于临界图的独立数的一个结论,利用图的1-因子和几乎1-因子存在的充要条件,采用结构图论的方法证明了：1）若G是2n阶△～临界图,且△≥n,δ≥n-2,则G存在1-因子;2）若G是2n＋1阶△-临界图,且△≥n＋1,δ≥n-2,则G存在几乎卜因子．     

某些图的线性荫度问题

线性森林是所有分支都为路的图,图G的线性荫度la(G)也就是把图的边集分解为互不相交的线性森林的最少数量k.一个图的线性荫度或者为[Δ(G)/2]或者为[Δ(G)+1/2].如果一个图G的线性荫度为[Δ(G)2],则称此图是第一类的;否则称为是第二类的.这里给出了关于某些第二类图的一个必要条件.     

关于3-圈不重点的平面图全染色的一个结论

给定一个图G，G的全k可染色是指至多用k种颜色，对G的顶点和边同时进行染色，使得相邻的或相关联的两个元素（点和边）不染同一颜色。图G的全染色数xτ（G）是指使G全k染色的最小整数k。△（G）是G的最大度，显然任何一个图不会是全△可染的，但是Vizing猜测任何一个图一定是全△＋2可染的。而这个全染色猜想，对平面图也仍是没有得到解决的。本文利用欧拉公式和重新分配的方法，对3-圈不重点的平面图进行了讨论，得出结论：最大度△≥8的任何两个3-圈不重点的平面图一定是全△＋1可染的。     

棒棒糖图的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指数的一个排序．     

在空间曲面上的警察抓强盗游戏

本文对能嵌入到各空间曲面族的图G,分别求出它们的警察数C(G)的上界,最后得到包含以上各种情况的一个统一公式,即定理9 如果G能嵌入到(?),m,n上,则c(G)《(1+「m/2」)×2n+3。     

变换图G^＊xy的独立数

变换图的概念由全图推广而来。文章在中图的补图M^-（G）的定义启发下,定义了四类变换图,其中一个恰是M（G）,并探讨了这些变换图的独立数。研究了变换图G^＊-＋的独立数与原图最大度的关系,以及G^-＋＋与G^-＋-的独立数与原图边独立数的关系。     

Sm∨Fn的全色数

设G（V,E）是阶数至少是2的简单连通图,k是正整数,若厂是从V（G）∪E（G）到{1,2,…,k}的一个映射,使得：对于任意的uv,vw∈E（G）,u≠w,有f（uv）≠f（vw）;且对于任意的uv∈E（G）,u≠v,有f（u）≠f（v）,f（u）≠f（uv）,f（v）≠f（uv）,则称f为G的一个k-全染色（简记成k-TC of G）．而Xt（G）=min{k｜k—TC of G},称为G的全色数．设G和H是点边都不相交的简单图,V（G∨H）=V（G）∪V（H）,E（G∨H）=E（G）∪E（H）∪{uv｜u∈V（G）,v∈V（H）},则称G∨H是G与H的联图。给出m＋1阶星和n＋1阶扇的联图的全色数。     

P部图的Kirchhoff指标下界

连通图G的两个顶点i和j之间的电阻距离rij定义为通过用单位电阻来代替G中的每条边而构造出的电网络N中的节点i和j之间的有效电阻的阻值．图G的Kirchhoff指标Kf（G）定义为G中所有点对之间的电阻距离之和．得到了n阶p部图G=G（N1,N2,…,Np）（｜Ni｜=ni,i=1,2,…,p）的Kirchhoff指标下界,指出当G为完全p部图时达到下界;并进一步得到,在所有的n阶p部图中,图兰图的Kirchhoff指标最小．     

一类拟二面体群的三度Cayley图的正规性

有限群G的一个Cayley图X=Cay（G,S）称为正规的,如果右乘变换群R（G）在AutX中正规.决定Cayley图是否正规,对于确定它的自同构群的有重要意义.本文综合运用有限群的知识与图的组合技巧证明了一类4m阶拟二面体群G=〈a,b｜a2m=b2=1,ab=am＋1〉的3度无向连通Cayley图的正规性,其中m=2r,且r〉2,并得到该类正规Cayley图.     

图的谱半径的一些下界

利用矩阵的相似变换,研究了简单连通图的谱半径的可达下界,得到一个新的下界ρ（G）≥δ1＋t-s＋√（s＋t-δ1）2＋4s（δ2-t）/2,等号成立当且仅当G=~G1 G2,其中G1为n-i阶（δ1-s）-正则图,G2为i阶t-正则图。     

图的距离不大于2的点可区别的边色数的一个新的上界

用图论概率方法中的一阶矩原理和Markov不等式,对文献[6]的方法改造得到图的距离不大于2的点可区别的边色数的一个新的上界x' 2 vd(G)≤[nd(d-1)+nd/2(d-1)+1,d≥3,结果优于文献[6].     

图的最大拉普拉斯特征值的上界

设G=（V,E）是n阶简单连通图,D（G）和A（G）分别表示图的度对角矩阵和邻接矩阵,L（G）=D（G）-A（G）则称为图G的拉普拉斯矩阵。利用图的顶点度和平均二次度结合非负矩阵谱理论给出了图的最大拉普拉斯特征值的新上界,同时给出了达到上界的极图,并且通过举例与已有的上界作了比较,说明在一定程度上优于已有结果。