圈的2顶点扩张图的最大强直径的一个下界

给定一个无向图G,将G的每条边{x,y}用弧xy或yx替代后得到的有向图称为G的定向图．若连通图G在定向后是强连通的,则称该定向为G的强定向．使得G的所有定向图中强直径最大的定向称为G的最大强直径定向．文章给出了矿圈（其中n≥3）的2顶点扩张图的最大强直径的一个下界．     

完全分割图的最小直径定向

对于图G，记G的具有最小直径的定向图为G’，用K2[Kn,Km^-]表示由阶为n的团和阶为m的独立集构成的完全分割图．为了得到完全分割图K2[Kn，Km^-]的最小直径定向，首先给出Kn的一个定向Rn使得diam(Rn)=2，然后对Kn与Km^-之间的边也给出特殊的定向，并证明了下述结论：     

完全图强乘积的强半径和强直径

首先证明2个非平凡完全图强乘积是完全图且具有强定向性,然后确定了完全图强乘积的最小强半径和最小强直径的精确值,给出了最大强直径和最大强半径的范围.最后通过利用强乘积的结合性,将上述结论推广到多个完全图的强乘积.     

Split完全图的最小直径定向

利用n 部完全图定向问题的结论，研究一类特殊图——split完全图的最小直径的定向问题，得到split完全图满足2 直径定向的条件及构作.     

图是λ′最优和超级λ′的充分条件

设G是有限简单无向图,使G-S的每个分支都不含孤立的边割S称为G的限制边割.G的限制连连通度λ′(G)是G的限制边割之中最少的边数,定义ξ(G)=min{d(x)+d(y)-2;xy∈E(G)}为G的最小边度.如果λ′(G)=ξ(G),则称G是λ′最优的.若任意最小限制边割都弧立一边,则称图G是超级λ′的.应用范型度条件给出了图是λ′最优和超级λ′的令分条件.     

图的相邻强边着色数

如果在一个图的正常边着色中,相邻两点关联的边集所着的颜色集合不同,则称此正常边着色为相邻强边着色.对图G进行相邻强边着色所需要的最小色数称为G的相邻强边着色数,记作X'as(G).给出了相邻强边着色数的两个上界:一是对于任何d-正则图G(d≥3),X'as(G)≤16d;二是如果图G有两个边不交的完美匹配,则X'aa(G)≤3△(G) 1.     

一类乘积图的Pfaffian性

给图G的边任意一个定向,如果该有向图对应的斜邻接矩阵的行列式等于图G的完美匹配数的平方,那么就称这个定向是Pfaffian定向,图G称为Pfaffian图.研究Pfaffian图的意义在于它的完美匹配数能在多项式时间内得到.该文通过证明给出的定向是Pfaffian定向的方法证明了一类偶剖分图与三个顶点的路的乘积图是Pfaffian图.     

星和完全等二部图联图的邻强边染色

对于1V（G）≥31的连通图G（V，E），若缸正常边染色法满足相邻的边染色集合不同，则称该染色法为缸邻强边染色法，其最小的称为G的邻强边色数。本文用特殊的方法记图的染色，并得到了星和完全等二部图联图的邻强边色数。     

路与路联图的邻强边染色和均匀邻强边染色(英文)

对于图G的一个正常边染色c,如果相邻的点所关联的边集的色集不相等,c称为邻强边染色.图G的邻强边染色所需要的最小值称为图G的邻强边色数.如果每个色类所含的边数最多差一,c被称为均匀边染色,其最小值称为图G的均匀边色数.论文确定了路与路联图的邻强边染色数和均匀邻强边染色数.     

直径为3的图的最小特征值

设Y是一个图集合,若对于Y中的所有图中,图G的最小特征值可以达到最小,则称G是集合Y中最小特征值的极小图。本文刻画了直径为3的n阶连通图最小特征值及其极小图。     

圈的定向距离图的性质

图G的两个定向D与D’的定向距离d0（D，D＇）是指与D’同构的定向与D之间不相同的弧数的最小值．G的定向距离图D0（G）的顶点是互不同构的定向，如果d0（D，D＇）=1，则D与D在D0（G）中相邻，并获得定向距离图D0（Cn）的性质．     

一些乘积图的覆盖数

在图上进行小石块的移动的步骤为从一个点上取走两个小石块,并在它的某个邻点上放一个小石块.显然存在某个自然数,当图的所有点上的小石块的总数大于或等于它时,无论小石块在图上是如何初始分布的,都可以经过一系列的上述步骤,使得每个点上都至少有一个小石块.对一个图而言,满足此条件的最小的自然数即为此图的覆盖数.解决了字典乘积图和一些强乘积图的覆盖数问题,并给出了任意一个图的关键点与直径的两个端点之间的关系.     

竞赛图满足(A)dám猜想的一个充分条件

对于竞赛图G=(V,A),证明了如果存在一弧xy满足条件:(1)y到x有长度为2的路径;(2)x到y没有长度为2的路径,则反向弧xy后G中圈的个数减少,即G满足(A)dám猜想.     

子图的度和与Hamilton圈

摘要对图G的一条边w,它的度记为d（uv）：tN（u）uN（v）＼{u,v}．笔者证明了对一个n阶2一连通图G,如果对任意两条不相邻Ⅻ和xy有d（w）＋d（xy）≥n-2,则G有Hamilton圈或Dominating圈．     

图的邻点可区分染色猜想成立的两个充分条件

简单连通图G的邻点可区分全染色(邻强边染色)是图G的一个正常全(边)染色,并且使得任意两个相邻的点u,v满足C(u)≠C(v),其中C(u)={f(u)}∪{f(uw)|uw∈E(G),w∈V(G)}(C(u)={f(uw)|uw∈E(G),w∈V(G)}).满足图G有一个邻点可区分全染色(邻强边染色)所用的最少颜色数记为χat(G)(χ′as(G)).图G的最大度记为Δ(G).本文给出了χat(G)=Δ(G)+3的一个充分条件和χ′as(G)=Δ(G)+2的一个充分条件.     

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的边幻和标号以及超边幻和标号,并给出了相应的证明.     

强乘积图的连通度

用k1＞0和δi表示图Gi(i=1,2)的连通度和最小度,给出了无向图强乘积的连通度一个下界κ(G1(□×)G2)≥min{κ1(1+δ2),k2(1+δ1)}.     

无K_(1,t)图的L(d,1)-T标号

给定一个连通图G=(V,E)及其一棵支撑树T,图G的一个L(d,1)-T标号即函数g:V(G)→{0,1,2,…},满足:(1)如果xy∈E(G),则|g(x)-g(y)|≥1;(2)如果dG(x,y)=2,则|g(x)-g(y)|≥1;(3)如果xy∈E(T),则|g(x)-g(y)|≥d.假设图G有一个L(d,1)-T标号函数g:g(V){0,1,2,…,k},则图G的所有L(d,1)-T标号函数中最小的整数k记为L(d,1)-T标号数λdT(G,T).本文证明了若G是无K1,t(3≤t≤n)的连通图,其最大度为Δ,|G|=n,T为G的任意支撑树,则λdT(G,T)≤tt--12Δ2+Δ+2d-2.