△(G)=4的平面连通图的存在性及其分布区域

本文证明了两个关于最大度为4的平面连通图的存在性定理,并确定了此图类的三种类型的分布区域。     

论图的连通负荷（Ⅰ）

本文提出了图的连通负荷概念，这是一个刻划图的连通性的新不变量。本文在建立连通负荷的界的基础上，讨论了连通负荷与图的结构的关系。     

4连通无爪图的最大圈长的一个下界

设Ｇ为ｎ阶４连通无爪图，σ５＝ｍｉｎ，则ｃ（Ｇ）≥ｍｉｎ（ｎ，σ５－７）。     

一类高度图的均匀色数

Ｗ．Ｍｅｙｅｒ猜想,设ｎ阶通图Ｇ的最大度为△（Ｇ）,且Ｇ不为完全图和奇圈,则图Ｇ的均匀着色数Ｘｅ（Ｇ）≤△（Ｇ）。本文证明了当△（Ｇ）≥ｎ－３时,此猜想成立。     

4连通图中可去边的分布

图的可收缩边与可去边是研究连通图的构造和使用归纳法证明连通图的一些性质的有力工具．本文利用边点割端片的性质给出某些4连通图中在特定子图上可去边的分布情况，得到了4连通图图上存在至少两条可去边的更一般的充分条件，改进了吴吉昌等的结果．同时给出4连通图4圈上和边点割原子及分离对上的可去边的分布．     

△(G)≥6的Halin图的点强全染色

图G(V，E)的正常k-全染色σ称为G(V，E)的k-点强全染色当且仅当A↓v∈V(G)，N[v]的元素染不同色，其中N[v]={uluv∈EG)}∪{v}，xT^vs(G)=min{k|存在G的k-点强全染色}称为G(V，E)的点强全色数。本文证明了：对于△(G)≥6的Halin图G(V，E)，有xT^vs(G)≤△(G) 2，其△(G)表示图G的最大度。     

二连通三正则简单图的最大亏格及结构性质

已知二连通三正则简单图的最大亏格至少为其圈秩的三分之一。且，此下界可以达到。本文表明这种达到最大亏格下界的图具有特殊结构，而且其结点数可被三整除。同时，还证明了当了点数不可被三整除时，这种图最大亏格的下界可提高一个亏格。     

非连通图C_4(m,0,0,0)∪G的优美性

讨论了非连通图C4(m,0,0,0)∪G的优美性,给出了非连通图C4(m,0,0,0)∪G是优美图的两个充分条件.其中C4(m,0,0,0)表示圈C4的(m,0,0,0)-冠.     

变换图G++-的连通度

本文所研究的图G的变换图G++-是以V(G)∪E(G)作为顶点集的图,它的两个顶点u与v被一条边连接当且仅当下列情形之一成立:(ⅰ)如果u,v∈V(G),那么它们在G中邻接.(ⅱ)如果u,v∈E(G),那么它们在G中邻接.(ⅲ)如果u与v一个属于V(G)而另一个属于E(G),那么它们在G中不关联.文章给出了变换图G++-的连通度的一个下限.     

一类极大临界4连通图的结构

引入图的粘合的概念,讨论了极大临界4连通图的性质,给出了一个图是这类图的一个充分必要条件,由此给出该类图的一种新的构造方法.     

非连通图C（2）4k+2∪Gm的优美性

证明了：当 k ≥1时,非连通图 C (2)4k+2∪ Gm 是优美图,其中 Gm 是任意一个有m 条边的优美图。     

非连通图（P3∨■）∪G及（C3∨■）∪G的优美性

将k-优美图的概念进行了推广,引入A～B优美图的概念,并以此为基础,得到了非连通图(P3∨■)∪G及(C3∨■)∪G是优美图的一个充分条件。证明了对任意正整数k,m,n,t,当k≤n≤t,n+k-1≤m时,图(P3∨■)∪(∪kj=1Kn,t)和(C3∨■)∪(∪kj=1Kn,t)是优美图;当k=1,2,2≤n<2m+1时,图(P3∨■)∪∪kj=1P(j)n,(C3∨■)∪∪kj=1P(j)n和(P3∨■)∪Pn∪St(t)是优美图;当2≤n≤2m+1时,(C3∨■)∪Pn∪St(t)是优美图。本文的结果推广了现有的一些结论。     

关于最大亏格达到下界的三连通三正则简单图

已被证明二连通三正则简单图的最大亏格至少为其圈秩的三分之一。且，当节点数可被三整除时，这个下界可以达到。本文提供了达到最大亏格下界的三连通三正则简单图所具有特殊结构，这就是三角形因子。     

3连通图的可去边的分布

e是3连通图G的一条边,如果G-e是某个3连通图的剖分,则称e是G的可去边。研究了3连通图的去边的分布规律,得到：（1）是阶至少为6的3连通图G中的一个圈,如果C上不存在3个连续的3度点,那么C上至少有两条可去边。（2）设T是阶至少为5的连通图G的一棵生成树,如果G中至多存在一个极大半轮,那么T上至少有一条可去边。由此可得：阶至少为5的3连通3正则图的生成树上至少有一条可去边。     

存在完美匹配4正则连通图的分类

本用Tutte定理对存在完姜匹配的4正则连通图给以明确分类,并由此得出关于4正则连通图完美(极大)匹配的一些重要性质．     

非连通图C4m∪G 的优美标号

讨论了非连通图C4 m∪G的优美性,给出了非连通图C4 m∪G是优美图的4个充分条件:当图G是缺标号值k+3 m且特征为k的交错图时,非连通图C4 m∪G存在着缺标号值k+1的优美标号;当图G是缺标号值k+m+1且特征为k的交错图时,非连通图C4 m∪G存在特征为2 m+k+1缺标号值k+1的交错标号;当图G是缺标号值k+2 m且特征为k的交错图时,非连通图C4 m∪G存在缺标号值k+3 m的优美标号;当图G是缺标号值k+2 m+1且特征为k的交错图时,非连通图C4 m∪G存在缺标号值k+m的优美标号。     

4连通无爪图的最长圈

设Ｇ为ｎ阶４连通远爪图，δ＝ｍｉｎ（ｄ（ｘ）／ｘ∈Ｖ（Ｇ）），则当ｎ≤６δ－１１时Ｇ为Ｈ图，当ｎ≥６δ－１０时，ｃ（Ｇ）≥５δ－７。     

平面三角剖分图的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-△。