整数距离图G（Dm，3）的点线性荫度

整数距离图G（D）以全体整数为顶点集，顶点u，v相邻当且仅当│u-v│∈D，其中D是一个正整数集．对于m〉3，设Dm，3={1，2，…，m│＼│3}，本文得到了G（Dm,3）的点线性荫度的上界和下界并决定出了它在某些较小的m上的确切值．     

关于某些新的非协调图

Graham和Slone引入了协调图的概念。一个具有q条边的图G是协调图 ,如果有一个从G的顶点集到模 q的整数群的一个单射 ,使得当每一条边xy被分配标号f(x) +f(y) (modq)时 ,所产生的边标号是不同的。利用数论的方法证明了一些新的非协调图     

关于最小度至少为3的图的全控制数

设G是一个没有孤立点的简单图.G的顶点集的一个子集S是一个全控制集,如果G的每个顶点都相邻于S中的某个顶点.图G的全控制数,用γt(G)来表示,是G的全控制集中的顶点数最少的全控制集的顶点数.证明了如果G是一个最小度至少为3的图,那么γt(G)≤n/2.从而证明了Favaron, Henning, Mynhart和Puech提出的一个猜想成立.     

关于某些新的非协调图

Graham和Slone引入了协调图的概念。一个具有q条边的图G是协调图,如果有一个从G的顶点集到模q的整数群的一个单射,使得当每一条边xy被分配标号f(x) f(y)(mod q)时,所产生的边际标号是不同的。利用数论的方法证明了一些新的非协调图。     

一类含奇数个顶点的三色有向图的本原指数

一个三色有向图D是本原的,当且仅当存在非负整数h,k和l,且h k l>0,使得D中的每一对顶点(i,j)都存在从i到j的(h,k,l)-途径,并称h k l的最小值为D的本原指数.研究了一类特殊的三色有向图,其含有奇数个顶点,其未着色图恰含一个n-圈、一个(n-2)-圈和一个2-圈,给出了在一种本原条件下的三色有向图本原指数紧的上界.     

一类含有两个圈的双色有向图本原指数

一个双色有向图D是本原的,如果存在非负整数h和k,且h k＞0,使得D中的每一对顶点(i,j)都存在从i到j的(h,k)-途径,则称h k的最小值为D的本原指数.本文考虑了一类特殊的双色有向图,它的未着色图有(m n)个顶点,包含一个m-圈和一个n-圈,给出了本原条件和指数上界,并对达到指数上界的极图进行了刻划.     

关于图是[a,b;m]-均匀图的一个邻域条件

设G是一个n阶的图,并设a和b是整数,使得1≤a＜b,以及δ(G)是G的最小度.证明了:如果δ(G)≥a 1,n≥2(a b)(a b-1)/b,以及ING(x)UNG(y)l≥an/(a b-1) 2对G的任意两个不相邻的顶点x和y都成立,那么G是一个[a,b;m]-均匀图.     

关于图的(g,f)-因子分解的若干结果

对目前关于图的因子分解研究中的3个问题进行了讨论,得到了以下结果(1)设Z= {x∈V(G) dG(x) - mg(x)≤t(x), 或mf(x) - dG(x)≤t(x);t (x) = f (x)– g (x) > 0}.当Z≠SymbolFCp时,g和f可以不全为偶数,能使(mg, mf)-图有(g, f)-因子分解.(2)G是具有2n个顶点的m-正则图,m ≥n.若(P1,P2,…,Pr)是m的一个划分,则G的边集E(G)能划分成r个部分E1,E2,…,Er,使G[Ei]是G的Pi-因子,其中Pi ≡ 0 (mod 2),I= 2,…, r;P1 ≡m (mod 2).(3)G是具有2n个顶点的m-正则图,m≥n.若G不含有K3,则G有1-因子分解.     

单圈图中一些基于距离的拓扑指标

对于一个连通图G,V(G)代表图G的顶点集,dG(u,v),δG(v)分别代表顶点u与v在图G中的拓扑距离和顶点v在图G中的度。主要讨论了3个基于距离的拓扑指标,分别是Wiener指标、Schultz指标和改进的Schultz指标,具体给出一个给定围长的单圈图的上述3个指标,并且给出它们之间的关系。     

一类路图的哈密尔顿圈

设G是一个图,我们用Π_k(G)表示G中所有具有k个顶点的路P_k所成之集。图G的路图P_k(G)有顶点集Π_k(G),且P_k(G)中的两个顶点相邻表示两条路P_k的并形成G中的一条路P_(k+1)或一个圈C_k。H.J.Broersma和C.Hoeda研究了路图的一些性质,并提出了两个猜想:1)若T是一颗树,△(T)≥4,则P_3(T)不是哈密尔顿图;2)若G是唯一圈图,△(G)≥5,则G不是哈密尔顿图。在本文中,我们证明了这两个猜想是对的。     

一类单圈图的度距离

图G=(V,E)表示顶点集为V、边集为E的所有的简单连通图的集合,研究了棒棒糖图L(n,k)的度距离,L(n,k)是将一条长为n-k的路的一个端点连接到圈Ck的一个顶点v上得到的一类特殊的单圈图。     

求图的最小顶点覆盖集的一个近似算法

已有的求图的最小顶点覆盖集近似算法或者近似比较高,或者为降低时间复杂度限制了图的规模.根据顶点的度分析了图的局部结构特征,提出了悬挂链、封闭链和稠部等重要概念,并在这些概念的基础上提出了相应的3个伪最小覆盖点选取启发式策略.运用这些伪最小覆盖点选取启发式策略设计了一个近似算法.该算法不限制图的规模,时间复杂度为O(|V|2),近似比为4/3,接近已知的可能的近似比下界1.1666,低于2005年认为最低的近似比1.361.与同类算法相比,该算法设计思路清晰,容易理解,易于编程实现,执行效果好,是图的最小顶点覆盖集问题的近似算法的一个重要补充.     

图与其补图Q谱半径之和的上界

设G为n阶简单图,利用边数m,最小、最大顶点度δ和Δ以及色数k给出了G与其补图-G的Q谱半径之和的上界,当G不含孤立点时有:2(n-1)≤ρ(Q(G))+ρ(Q(-G))≤2(Δ-δ+n-1)和ρ(Q(G))+ρQ(-G))≤2n-3+2-12(n-1)n,其中t=min{k,-k}。当-G含l个孤立点时有:ρ(Q(G))+ρ(Q(-G))≤2n-3+2-1k(n-1)2+l,同时给出了图G与其补图-G的拉普拉斯谱半径之和的一个上界。     

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指标最小．     

全制约数的上界

设Ｇ＝（Ｖ，Ｅ）是无孤立点的简单图．设Ｔ是Ｖ的子集，如对任意Ｕ∈Ｖ，存在ｕ∈Ｔ使得ｕｖ∈Ｅ，则称Ｔ为Ｇ的全制约集．全制约集的最小基数称为Ｇ的全制约数，记作γｔ（Ｇ）．本文证明了如Ｇ是阶数ｎ≥３，最小度至少为２的连通图，则γｔ（Ｇ）≤４「（ｎ＋ｌ）／７」     

图的一类全标号

本文证明了最小度至少为2的简单图,总可以使点和边的标号满足全不相同且点的标号恰为其邻边的标号之和.     

关于一类新的整和图

Ｈａｒａｒｙ 提出了整和图的概念,设 ｆ 为整数集到图 Ｇ（ Ｖ（ Ｇ） , Ｅ（ Ｇ）） 的顶点集 Ｖ（ Ｇ） 之间的一个单射,使得对于 Ｇ 的两个不同的顶点ｕ 和ｖ ,ｕｖ ∈ Ｅ（ Ｇ） ,当且仅当存在 ｗ ∈ Ｖ（ Ｇ） ,使 ｆ（ ｕ） ＋ ｆ（ ｖ） ＝ｆ（ ｗ ） ,则 Ｇ 称为整和图,并且他证 明了所有路 和星图是整 和图。树 中度数至少 为３ 的 顶点称为 叉点, Ｃｈｅｎ 用粘合法证明了广义星图和叉点距离至少为４ 的树是整和图,并同时猜测所有的树均为整和图。本文证明了所有叉点距离至少为３ 的树是整和图,从而给出了一类新的整和图     

关于可行图的几个新结论

设有n个集合X1,X2 ,… ,Xn,一个以X =∪ni=1Xi 为顶点集的图G称为是一个关于集合序列 (X1,X2 ,… ,Xn)的可行图 ,如果对每一个Xi(i=1 ,2 ,… ,n) ,导出子图Gi=G[Xi]是连通的。集合序列 (X1,X2 ,… ,Xn)含最少边数的可行图称为关于 (X1,X2 ,… ,Xn)的最小可行图。将n =3推广至任意的自然数n ,得出了集合序列 (X1,X2 ,… ,Xn)的最小可行图G =∪ni=1Gi,当满足∩ni=1Xi≠Φ时 ,G是关于集合序列 (X1,X2 ,… ,Xn)的最小可行图的一个充分必要条件 ,同时得出了集合序列 (X1,X2 ,… ,Xn)的最小可行图在某种条件下的两个主要结果。     

几类特殊图的（2,1）-全标号

研究了与频道分配有关的1种（p,1）-全标号染色问题.（p,1）-全标号是从V（G）∪E（G）到集合{0,1,…,k}的1个映射,满足：①G的任2个相邻的顶点得到不同的整数;②G的任2个相邻的边得到不同的整数;③任1个点和与它相关联的边得到的整数至少相差p.通过在2个简单图之间叠加一系列匹配构造了几类有趣图,并根据所构造图的特征,利用穷染法得到了这些图的（2,1）-全标号数.