连通图的度距离和Wiener指数

令P+(n)表示圈没有公共边的n阶连通图的集合,P+(n,m)表示P+(n)中具有m(m≥1)个极小圈的连通图集合.证明了当n≥6时,P+(n,m)中具有最小度距离的图是花F(n,m),它是m个具有一个公共顶点的三角形并在公共顶点粘上n-1-2m条悬挂边的图;同时证明P+(n)中具有最小度距离的图是F(n,1),它是一个三角形并在一个顶点上粘n-3条悬挂边的图.     

k-连通图中存在哈密尔顿圈的一个隐度条件

文中给出了强基本独立集的概念,并证明了如下定理:设G是一个具有n个顶点的k-连通图,其中k≥2.如果对任意一个具有k个顶点的强基本独立集S,都有max{d1(x)|x∈S}≥n/2,则G是哈密尔顿图.此定理推广了已有的几个有关图中哈密尔顿圈存在性的定理.     

k-连通无爪图中存在哈密尔顿圈的一个隐度条件

文中给出了强基本独立集的概念,并证明了如下定理:设G是一个具有n个顶点的k-连通无爪图,其中k≥2.如果对任意一个具有k个顶点的强基本独立集S,都有max{d2(x)|x∈S}≥n 2,则G是哈密尔顿图.此定理在无爪图的条件下推广了已有的几个有关图中哈密尔顿圈存在性的定理.     

非连通并图的优美标号研究

设图G3是长度为3的圈C3或为含3个顶点的路P3,文章给出了非连通图(G3∨Km)∪Kn,t和(G3∨Km)∪Pn,并证明了对任意正整数m,n,t,如果min{n,t}≤m,则图(G3∨Km)∪Kn,t是优美图;如果2≤n≤2m+1,则图(G3∨Km)∪Pn是优美图;同时证明了对任意正整数m,n,图(G3∨Km)∪St(n)和(G3∨Km)∪W2n+5是优美图.其中,Pn是n个顶点的路,G1∨G2是图G1与G2的联图,Km是m个顶点的完全图,m是Km的补图,Kn,t是具有二分类(X,Y)的完全偶图,且|X|=n,|Y|=t,St(n)是具有n+1个顶点的星形树,Wn是具有n+1个顶点的轮图.     

含环三圈双色有向图的本原指数

考虑了一类特殊的双色有向图,它的未着色图含有n个顶点,且包含一个n圈和两个（n 1）圈,在每个顶点上有环.给出了本原条件和指数上界.     

2类包含K4的优美国及其注记

利用计算机为辅助工具,分别给出了2类包含图K4的图K4＋Gn 1和K4＋Kn,n的优美标号,从而证明了图K4 Gn 1和K4＋Kn,n是优美图,并由K4 Kn,n的优美性给出了边数为m的极小优美图的顶点数f(m)的范图是｛(1＋√8m 1)/2｝≤f(m)≤｛2（√m 3-1)｝.     

几类极图谱半径序列的极限

讨论几类极图谱半径序列的极限问题,给出n个顶点的路Pn和回路Cn的拉普拉斯谱半径在n递增时的极限,以及在最大度为Δ的n个顶点的树中、邻接谱半径最小的树和邻接谱半径最大的树的邻接谱半径在Δ固定n递增时的极限.     

一类双色有向图的指数

研究一类特殊的本原双色有向图,其未着色的有向图有2n 1个顶点,包含一个(2n 1)-圈和一个(n 1)-圈.给出了这个双色有向图的指数的边界和极图的刻划.     

图的最小严格强控制数

设K1,n为星图,K1,n+me为K1,n任意加m条边所得到的图.首先研究了K1,n的严格强控制数,K1,n+e的严格强控制数;其次研究了形如K1,n+me的图类中图的最小严格强控制数以及此类图中达到最小严格强控制数的极小图;最后给出具有n个顶点的图类中图的最小严格强控制数.     

2类包含K4的优美图及其注记

利用计算机为辅助工具,分别给出了2类包含图K4的图K4+Gn+1和K4+Kn,n的优美标号,从而证明了图K4+Gn+1和K4+Kn,n是优美图,并由K4+Kn,n的优美性给出了边数为m的极小优美图的顶点数f(m)的范图是{(1+√8m+1)/2}≤f(m)≤{2(√m+3-1)).     

给定悬挂点数图的Wiener指数的极图

设G是一个简单图,图G的Wiener指数是G中所有顶点的距离之和。本文刻画了给定顶点数和悬挂点数的图类中,Wiener指数取到最小、次小、第三小的极图,并由此确定了关于悬挂点数的Wiener指数的下界。     

双星图的Ramsey数的上界

对给定的两个图G和H,Ramsey数R(G,H)是最小的正整数N,使得对完全图KN的边任意红/蓝着色,则或者存在红色子图G,或者存在蓝色子图H.双星B(m,n)为直径是3,有两个中心顶点,其顶点度分别为m+1和n+1的树.得到,当nm时,R(B(m,n))2n+m+2;当n=m或n=m+1时,R(B(m,n))=2 m+n+2.     

直径为n-4谱半径第二小的连通图

采用图形变换和比较图的特征项式等方法,按照图的最小谱半径对具有固定直径和顶点数的图类定序,确定了顶点数为n直径为n-4谱半径是第二小的连通图.     

给定悬挂点的非像星树的谱半径

设(J)n.k表示具有n个顶点和恰有κ个悬挂点的非像星树的集合,利用比较特征多项式的方法刻画出了(J)n.k中谱半径最大的树.     

与T(1,2,n)的补图有相同色划分的图

研究了树图的伴随多项式根的分布规律,并利用此结果完整地刻画了与T(1,2,n)的补图有相同色划分的图,其中Tn(l1,l2,l3)表示只有一个3度点,三个1度点且惟一3度点到三个1度点的距离分别为l1,l2和l3的n阶树.     

RP图的特征刻划

设T是图G的一颗支撑树,若某顶点u满足;对任意顶点υ均有dG(u,υ）=dT(u,υ）,则称u对于支撑树T是RP,如果对G的任一棵支撑树都至少存在一个RP点,则称图G是RP图,Gagliardi等在1997年证明了K2,n是一类RP图,并猜想：“K2,n以及在其顶点上加上若干树状结构所得的图是仅有的RP图”。但容易验证圈Cn也是一类RP图,因此上述猜想需要修正,本文证明了RP图的如下特征刻划：除树外,简单图中只有K2,n和Cn 以及在某若干顶点上分别外接互不相交的树状结构所得的图是RP的。     

与T(1,1,n)的补图有相同色划分的图

应用图的伴随多项式理论完整地刻画了与T(1,1,n)的补图有相同色划分的图,其中T(l1,l2,l3)表示只有一个3度点,三个1度点,且唯一3度点到三个1度点的距离分别为l1,l2,l3的n阶树.     

一类树的拓扑指标极值

具有r个悬挂点的树是r叶树.研究具有n个顶点4叶树的Merrifield-Simmons指标,刻画具有第四至第六小Merrifield-Simmons指标的4叶树.     

Ln,p图的代数连通度

Kp表示p阶完全图.选取Kp的任意r个顶点分别点粘接r棵树,得到n阶图Ln,p.所有n阶图Ln,p的集合记为（L）n,p.代数连通度是刻画图的连通性的重要参数,笔者分别确定了Ln,p中具有最大、最小和第二小代数连通度的图.     

具有k个悬挂点的双圈图的Harary指数

双圈图是指顶点数等于边数减1的连通图,Harary指数是指图中所有顶点对的距离倒数之和.基于此,主要研究了具有k个悬挂点且两个圈只有一个交点的n阶双圈图有极大Harary指数的图类.