路图P3(G)的色数

设G是一个图,G的路图P3(G)的顶点集是G中所有三个顶点的路P3, 当G中的两个P3路形成P4路或C3圈时,在P3(G)中它们所代表的两个顶点相邻. 在这篇文章中,我们得到对于一个无三角形的图G, χ(P3(G))≤β(G),其中β(G)表G的点覆盖数. 对于顶点数至少为3的连通图G,χ(P3(G))≤2当且仅当G是二部图, 并且χ(P3(G))=1当且仅当 G是星图. 对于K4的剖分图G,2≤χ(P3(G))≤3. 对于系列平行图和外可平面图G,χ(P3(G))≤3.     

关于线图上的等距圈和次泛圈

给定一个图G,且满足min{d(u)+d(v)u,u∈E(G)}≥8.有下结论若C是G中的圈且满足dc(u,v)=d(u,υ),(A){u,v}(∈)V(C).当任一这样的圈C的长度不超过△(G)+1时,线圈L(G)是次泛圈的且所给的条件都是最好可能的.     

一类3—连通图的周长

设G=(V,E)是一个n阶无向简单图,本文证明了:设G是一个3-连通图,若G的每一个最长圈是控制圈,则G的周长c(G)≥min{n,2NC_2}或G同构于Petersen图,其中NC_2={|N(u)∪N(v)||u,v∈V(G),d(u,v)=2}。     

单圈图的N-G型的代数连通度的界

对任一个n阶单图G，用α（G）表示G的代数连通度，证明了对任一n阶单圈图G，有1≤α（G）＋α（G）．     

变换图G++-的超力连通性

对于图G,一般有λ(G)≤δ(G).如果λ(G)=δ(G),称图G是较大边连通的.如果G的每一个最小边割只能分离G的一个孤立点.称图G是超边连通的.本文证明了几乎所有的有限图G,其变换图G -都是超边连通的.     

关于3-连通图最长圈的注

设C是3-连通图G的一个最长圈,H是G-V(C)的一个分支满足|H|≥3.文献[4]在给H附加一些条件后,证明|C|≥2d(u) 2d(v)-5,并且不等式严格成立除非G属于某些例外图类,这里u,v是G中两个不相邻的顶点.本文给出了上述例外图类的精确刻划.     

Ramsey定理的一种推广

Ramsey定理指出:对于任何一个正整数k,存在一个最小的正整数r(k,k),使得对任意一个至少有r(k,k)个顶点的图G,它或者有k个顶点的完全子图Kk,或者有k个顶点是独立集.由此定理易得:设G是顶点数n>r(k,k)的简单图,其边数e>0,且G的所有k阶导出子图的边数相等,那么G是完全图.并给出上述结论的推广:设G是n(n≥4)阶简单图,其边数e>0,对某个给定的自然数k(2≤k≤n-2),若G的所有k阶导出子图的边数相等,则G是完全图.     

具有最小Wiener指数的三圈图（英文）

一个连通图的Wiener指数定义为图中所有点对的距离之和.主要研究了三圈图Wiener指数的下界问题,并刻画了达到下界的极值图.     

具有最小Wiener指数的三圈图

一个连通图的Wiener指数定义为图中所有点对的距离之和.主要研究了三圈图Wiener指数的下界问题,并刻画了达到下界的极值图.     

互补自中心图

在第4届国际图论会议上(1980.5 Michigan) J, AKIYAMA和F. HARARY'"综述J’满足性质p的图G及其补图G的研究现状,并指出,尚有很多性质p的问题一可提出.我们考察p是一个图的自中心性.Buckley' 2’曾指出:寻找自中心图的特征是一个十分困难的工作.Copobiancol”把它列入未解决的图论问题之一本文研究图G及其补图G的自巾心性,刻划G和G均具有白中心性的图的一系列特征,找出了构造自补自中心图的一般方法,并去构浩自巾J广。因根供一条右扮徐径_水立所论的图均县有限It nu单图。夫加说明的IN论太     

具有完美匹配的单圈图第二大特征值的上界

得到了具有完美匹配的单圈图第二大特征值的一个上界．同时也给出了具有完美匹配的单圈图的第二大特征值的最大值的一个下界．     

化学单圈图的原子键连通性指数

图G的原子键连通性指数的定义如下:ABC(G)=∑uv∈E(G)((du+dv-2)dudv)(1/2).其中du、dv分别表示图G的边uv的2个端点u、v的度数.ABC指数已被证实为研究烷烃的稳定性以及环烷烃的应变能提供了一个很好的模型.讨论了n阶化学单圈图,给出了其ABC指数的可达的下界及其相应的极图     

关于临界h棱连通图的最大棱数及最大图的结构(Ⅱ)——临界h棱连通图的性质和最大临界3棱连通图类的刻划

设λ(G)表示G的棱连通度,图G称为临界h棱连通的,如果λ(G)=h而且对任何x∈V(G),λ(G-x)≤h-1,具有最大棱数的临界h棱连通图称为最大临界h棱连通图.本文首先证明对h≥3的临界h棱连通图的若干性质,然后证明最大临界3棱连通图的每个顶点都与3度点相邻,并由此给出了此类图的结构刻划和最大棱数.     

两类E~G形图簇的补图的色等价性定理

设G是任意的p阶连通图,用ΨG(i)(k,p)表示把图G的第i个顶点vi与星图Sk+1的k度点重迭后得到的图(1≤i≤p),给出了图ΨG(i)(k,p)与星图Sn+1组合而成的两类EG形图簇,并通过研究这些图簇的伴随多项式的因式分解,进而证明了它们的补图的色等价性定理。     

自余弱弦图

研究了一类自余(sc)弱弦图,即广义的自余弱弦图,得到了一些自余弱弦图的下边界和上边界.讨论了自余弱弦图的识别问题,特别地给出了一种O(m2)时间算法,能推断自余图是弱弦的还是非弱弦的,进一步作者编目了自余弱弦图的至少17种异体.     

单演半群的Γ图

对半群Cayley图的研究是近年来十分活跃的研究领域.定义了半群的Cayley图的一种推广图Γ图,刻画了单演半群的Γ图的结构,给出了单演半群的Γ图弱连通的一个充分必要条件.     

图的谱矩序列与图的排序

图的谱矩是代数图论中一个重要的代数不变量,本文通过计算图的第5、6阶谱矩,研究了图的结构与图的谱矩之阃的联系,动态地研究了图的结构变化(包括图的阶数的增大及同阶前提下所含圈长度的变化等)对谱矩序列排列的影响,给出了研究图依谱矩序列排序问题的新方法.     

3-连通P3-支配图的Hamilton性

引进了P3-支配图并对BROERSMA HJ和VUMAR E提出的作为半无爪图的一个超类,研究了这类图的一些性质.得到:若G是n阶3-连通P3-支配图,则当n≤5δ-4时,G是Hamilton图.     

J._C.Bermond等的一个定理的注

Ｊ．—Ｃ．Ｂｅｒｍｏｎｄ等在［１］中断言：有限阿贝尔群上的连通四正则Ｃａｖｌｅｙ图可分解为两个哈密顿圈的并．但在证明这个结果时，他们漏掉了两种情况．本文将补充其证明．     

卡氏积图的Laplacian谱半径的上界

对近年来图的Laplacian谱半径上界的研究成果进行了简单梳理.利用2个图的卡氏积图的特征值,讨论了2个循环图的卡氏积图的Laplacian谱半径的上界问题,得到了几个上界,推广了已有文献的结论.