无向广义De Bruijn图的m-限制边连通性

m-限制边割将连通图G分离成阶不小于m的连通分支,图G的最小m-限制边割所含的边数称为图G的m-限制边通度,记作λm（G）.对于包含m-限制边割的连通图G,有λm（G）≤ξm（G）（m≤3）;如果λm（G）=ξm（G）,则称图G是极大m-限制边连通的.本文证明：当n≥7时,无向广义De Bruijn图UBG（2,n）是极大m-限制边连通的（m={2,3}）.     

W_m与P_n（n≤3）联图的点可区别边色数

设G是简单图,图G的一个k-点可区别正常边染色f是指一个从E（G）到{1,2,…,k}的映射,且满足u,v∈V（G）,u≠v,有S（u）≠S（v）,其中S（u）={f（uw）｜uw∈E（G）}.数min{k｜G存在k-VDPEC染色}称为图G的点可区别正常边色数,记为χs′（G）,研究了Wm∨Pn（n≤3）的点可区别边染色,给出了Wm∨Pn（n≤3）的点可区别边色数.     

积图的点PI指标

图G的点PI指标PIv(G)=∑e∈E(G)v更近的点的个数。两图G和H的积图G∨H的点集是V(G)×V(H);点(a,b)和(c,d)是相邻的当且仅当a和c或b和d分别在G和H中是相邻的。文章给出了积图G∨H的点PI指标的表达式。     

k连通［s,t］图的Hamiltion连通性

若图G的任意个s顶点的导出子图至少有t条边,则称图G为[s,t]图．[s,t]图的概念可视为图的独立数概念的推广．本文证明：若图G是k连通[k＋1,2]（k≥2）图,则G或者是Hamilton连通的或者同构于Kk∨Gk．由此可以推出,若图G的阶是n（n≥3）,α（G）≤κ（G）－1,则G是Hamilton连通的．     

Cluster乘积图的点PI和Szeged指标

连通图G的点PI和Szeged指标分别定义为PIv(G)=∑e=uv∈E(G)[nu(e G)+nv(e G)]和Sz(G)=∑e=uv∈E(G)nu(e G)nv(e G),其中nu(e G)表示图G中到点u的距离小于到点v的距离的点的个数,nv(e G)表示图G中到点v的距离小于到点u的距离的点的个数.设G{H}和GoH分别表示两个图G和H的cluster乘积和corona乘积.利用因子图的相关拓扑指标分别给出计算G{H}和GoH的点PI和Szeged指标的精确表达式.     

强正则图的补图的能量

设G是一个n阶简单连通图,G的能量定义为G的特征值的绝对值之和．对于强正则图的能量研究,已有许多学者得到了一系列深刻的结果．本文研究具有参数（n,r,u,v）的强正则图G的补图G^-的能量问题,我们得到了一个不等式：2（n-r-1）≤E（G^-）≤（n-r-1）＋n/2／n-1.     

关于图的圈和退化圈分拆的一个注记

设G是一个n阶图，k是满足2≤k≤n的正整数，于是得到了如下结论：如果图G的任何一对不相邻的顶点{u,v}，都满足max{dG(u)，dG(v)}≥(n-k 3)／2，则存在k个点不交的子图Hi,使得V(G)=V(H1)∪V(H2)∪…∪(Hk)，其中Hi为一个圈或一个点或一条边．     

超立方体网络的限制边连通性

m-限制边割将连通图分离成阶不小于m的连通分支,图G的最小m-限制边割所含的边数称为图的m-限制边连通度.本文给出了n立方体的m-限制边连通度的表达式,由此推出：当m≤2（n/2）-1或m=2 k≤2n-1（k为任意正整数）时,超立方体Qn是极大m-限制边连通的.     

边-超欧拉图的一个度数和条件

图G称为边-超欧拉图,如果对于它的任一条边e,都有欧拉生成子图H包含e．给出了边-超欧拉图的一个度数和条件,即：设G是2一边连通的n个顶点的简单图,如果n≥100并且对于图G的任意两个不相邻的顶点u和v都有d（u）＋d（v）≥2/5n,那么对于图G的任意一条边e,或者G有欧拉生成子图H包含e,或者G（G关于e的剖分图）可以被收缩成K2.3或K2.5．     

一类R(G)=-2图簇的补图的色性探讨

研究图的色唯一性问题是图论的一个重要内容,利用图G的伴随多项式的末项的特点,探讨了一类n个点n＋1条边且R（G）=-2的不可约图补图的色唯一性的问题,证明了：设｜V（B2）｜=n（≥7）,若B2是不可约的且n≠8,则B2^-是色唯一的．     

Mycielski’s图的Co-PI指标

令G是一个图,u是图G的一个顶点, TG（ u）是图G当中除了u以外的其余顶点到点u的距离之和, T（ u）＝TG（ u）＝∑u∈V dG（u,v）,Co-PI指标定义为：Co -PIv（G）＝∑uv∈E（G） T（ u）-T（ v）。文章给出了一些Mycielski’ s图的Co-PI指标的计算公式。     

两个图的corona乘积图的Wiener极性指标

图G=（V,E）的Wiener极性指标是图G中距离为3的无序点对的数目。图G和H的点corona图，记为G°H是取G的一个拷贝和｜V（G）个H的拷贝，然后把G的每个点和其相对应拷贝的每个点相连而得到的图。图G和H的边corona图，记为G◇H，是取G的一个拷贝和｜E（G）｜个H的拷贝，然后把G的每条边的两个点和其相对应拷贝的每个点相连而得到的图。本文给出两个图的corona乘积图的Wiener极性指标。     

四角系统的一般Randidc标的下界

一个图（分子）G的一般Randic指标定义为图G的所有边上的权（d（u）d（v））^a之和，这里d（u）表示G中点u的度且α是任意一个实数．确定了有n块格子的四角系统的一般Randid指标在α≥1时的下界，并且给出了相应的极图．     

正则图Cartesian积的线图的秩

设G是一个顶点为n,度为r的正则图,那么它的边为m=1/2nr.G线图是顶点为m,度为（2r-2）,边为1/2nr（r-1）的正则图,本文研究两个正则图或强正则图的Cartesian积图的线图的秩,得到了许多结果,推广了G．J．Davis,G．S．Domke等人的结论．     

完全二部图K5，n的点可区别IE-全染色

设G是简单图,图G的一个k-点可区别IE-全染色（简记为k-VDIET染色）f是指一个从V（G）∪E（G）到{1,2,…,k}的映射,且满足：A↓uv∈E（G）,有f（u）≠f（v）;A↓u,v∈V（G）,u≠v,有C（u）≠C（v）,其中C（u）={f（u）}∪{f（uv）｜uv∈E（G）}。数min{k}G有一个k-VDIET染色}称为图G的点可区别IE-全色数,记为χut^ie（G）。本文给出了完全二部图K5,n（n≥6）的点可区别IE-全色数。     

Kneser图KG(11,5)平方图的色数

Kneser图KG(n,k)的顶点集包括一个n元集的所有k元子集,其中的任意两个顶点相邻当且仅当它们对应的子集不相交.一个图G的平方图G2的顶点集与G的顶点集相同,在G2中两个顶点之间有边当且仅当它们在G中的距离不超过2.通过理论分析和计算机搜索,得到8≤χ(KG2(11,5))≤10,10≤χ(KG2(13,6))≤16,其中前一个结论改进了已知的下界7和上界12.     

轮图的（2，1）-全标号

图G的一个后-（d,1）-全标号是一个映射f：V（G）∪E（G）→{0,1,…,k},使得任意2个相邻的点和相邻的边有不同的值,且任一对相关联的点和边的值的差的绝对值至少为d．G的（d,1）-全标号数λd^T（G）定义为G有一个K-（d,1）-全标号的最小的k值,得到了轮图的（2,1）-全标号．     

两类图的（d，1）-全标号

图G的一个k-（d,1）-全标号是一个映射f：V（G）∪E（G）→{0,1,…,k},使得任意2个相邻的点和相邻的边有不同值,且任一对相关联的点和边的值差的绝对值至少为d．G的（d,1）-全标号数λ^Td（G）定义为G有一个k-（d,1）-全标号的最小的k值,得到了扇图与轮图的（d,1）-全标号数。     

关于正则二部图的Pebblinq数

图G的pebbling数f（G）是最小的正整数n,使得不管n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把一个pebble移到图G的任意一个顶点上,其中图G的一个pebbling移动是从一个顶点移走2个pebble,而把其中的一个移到与其相邻的一个顶点上。证明了具有2m个顶点的k-正则二部图的Pebbling数为2m,其中k≥[（m＋1）／2]。     

树的最大与次小Laplacian特征值和的上界

随着计算机技术和网络技术的不断发展,图的谱被广泛应用于网络拓扑结构的特征分析,Laplacian矩阵的谱(特别是最大特征值和次小特征值)在网络结构中扮演重要角色.设G=(V,E)是一个具有n个顶点的简单图,A(G)为G的邻接矩阵,D(G)为G的度对角矩阵.定义G的Laplacian矩阵为L(G)=D(G)-A(G),设L(G)的特征值为μ1(G)≥μ2(G)≥…≥μn-1(G)≥μn(G)=0,最大特征值μ1(G)称为图G的Laplacian谱半径;次小特征值μn-1也称作图G的代数连通度.本文讨论了树的L(G)的最大与次小特征值和μ1(G)+μn-1(G)的上界,得到几个有意义的结论.