冠图G1. Km1,m2的邻接谱

给定简单图G1和G2,G1的顶点标记为v1,v2………,vn1.图G1和G2的冠图G1.G2被定义为取n1个G2的拷贝,然后连接vi与相应的G2的第i个拷贝中的每一个点(i=1,2………,n1)所得到的图.在文献[2]中,对连通图G1和任一正则图G2,S.Barik,S.Pati和B.K.Sarma给出了G1.G2的邻接谱的完整的表达式.继文献[2]的工作进一步考虑当G2是非正则图时冠图G1.G2的邻接谱.本文完全确定了冠图G1.Km1,m2的邻接谱,其中Km1,m2是完全二部图.     

自中心的几个定理

自中心图是每个顶点都是图的中心的图.关于自中心图的一般特征,目前除了由其定义直接可以推知的图的直径等于半径这个特征之外,尚未得到其它结果.因此[1]中将这个问题作为未解决的第20个问题提了出来.本文讨论了自中心图的一些特性,同时构造了几类自中心图,它们比已知的初等圈、完全图、不连通图和完全n-部分图等自中心图更广泛,并且包含了[1]中提出的那种自中心图。本文所讨论的图G都是指有限的、连通的、无自环和无多重边的无向图,其它术语     

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

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

互补自中心图

在第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是一个连通图.图的连通度κ(G)存在一个最小正整数k,使得FV,|F|=k且G-F不连通或是一个平凡图.如果每一个最小点割都孤立G的一个点,则图G是超连通的或超-κ的.定义没有孤立点的图G的逆度为R(G)=∑v∈V1/d(v).得到:设n阶连通图G,最小度为δ,若R(G)1+2/(δ+1)+(n-2δ-1)/((n-1)(n-3)),则G是超-κ的.     

关于直积图的坚韧度和边坚韧度的注记（英文）

图G的坚韧度t(G)定义为:对非完全图是t(G)=min{|S|/ω(G-S)|SV(G),ω(G-S)≥2},而对完全图是∞,其中ω(G-S)表示G-S的连通分支数.边坚韧度定义为t′(G)=min{|X|/ω(G-X)-1|X是G的边割集}.在本文中,我们给出了完全图和圈的直积图的坚韧度,并且提供了完全图和正则图类的直积图的边坚韧度公式.     

双广义Petersen图的可靠性分析（英文）

设G是连通图,图G的超连通度(超边连通度)是指从图G中删除最小数目的点(边)使得G不连通,且在G的每个分支中不存在孤立点.周进鑫和冯衍全(2012)首次提出了双广义Petersen图的概念,文章证明了双广义Petersen图DP[n,k]是超连通和超边连通的,以及当n?{2k,3}时,κ_1(DP[n,k])=λ_1(DP[n,k])=4.     

给定围长的图的超三限制性连通度的充分条件

图G是一个连通图.称X为三限制性割,如果G-X的每个连通分支至少有三个点.三限制性连通度k3(G)是三限制性割的最小基数,更进一步,如果图G的围长为4,去掉最小的三限制性割孤立出一条二长路,则称它是超三限制性连通的.本文给定了图是超三限制性连通的直径围长充分条件,还研究了超三限制性边连通图.     

列表双临界图（英文）

G是k-可着色的连通图,如果对于G中的所有边uv,都有G-u-v是(k-2)-可着色的,则称图G是双临界图.由Erdo?s和Lova′sz提出了一个长期未能解决的猜想:完全图是唯一的双临界图[1].连通图G称为边双临界图,如果G中包含多对不相邻的边,并且对于任意一对不相邻的边e1,e2,都有χ(G-e1-e2)=χ(G)-2,其中χ(G)表示图G的色数.Kawarabayashi等人[2]及后来的Lattanzio[3]证明了完全图是唯一的边双临界图.文章证明了在图G中,对于任意的两个点u,v∈V(G),如果ch(G-u-v)=ch(G)-2,则图G是完全图,其中ch(G)表示G的选择数,还证明了完全图是唯一的列表双临界图.     

图的非自中心数（英文）

许克祥等人在文献[1]中定义了新的基于离心率的图不变量,称之为图的非自中心数(简称NSC数),记为N(G).图的非自中心数定义为N(G)=∑_({v_i,v_j}V(G)|e_i-e_j|,这里ei表示顶点vi的离心率,在文献[1]中,同其他结果一起,作者确定了一些图的N(G)数的上界和下界并且刻画了达到上下界的极图.但是作者给出的极图的刻画是不完全的.基于他们得到的研究结果,在本文中我们给出了达到上下界的所有极图的完全刻画.另外,我们还给出了阶为n直径为d的树T的N(T)数的下界并且确定双圈图和含有奇数个顶点的三圈图的NSC数的上界.     

对称群上Cayley图的Hamilton性（Ⅱ）

对于每一个ｎ（≥３）阶连通简单图，都可定义一个相应的对称群上的Ｃａｙｌｅｙ图．本文继续文献［１］证明了每一个连通简单图对应的Ｃａｙｌｅｙ图都是一个Ｈａｍｉｌｔｏｎ图，从而在这方面的问题得到了圆满的解决．     

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

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

对称群上Cayley图的Hamilton性（Ⅰ）

对于每一个ｎ（≥３）阶连通简单图．都可定义一个相应的对称群上的Ｃａｙｌｅｙ图．本文为《对称群上Ｃａｙｌｅｙ图的Ｈａｍｉｌｔｏｎ性（Ⅱ）》做了准备工作，同时证明了若树Ｔ对应的Ｃａｙｌｅｙ图是一个Ｈａｍｉｌｔｏｎ图．则Ｔ任添一树叶对应的Ｃａｙｌｅｙ图也是一个Ｈａｍｉｌｔｏｎ图．     

路图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是简单图,用颜色1,2,3,…对G的边正常着色,如果在每一顶点表现的颜色构成一个连续的整数集合,那么就称这个着色是连续的.图G的亏度def(G)是粘在G上使得它可连续着色的悬挂边的最小数目.在本文中,我们完全确定了单圈图和双圈图的亏度.     

具有较小秩的带号图的刻画

带号图是每条边带有符号（正或负）的简单图.探讨了带号图的秩,刻画了秩为2与3的带号图,以及秩为4的带号二部图.     

上连通和超连通六次点传递图

图 G 称为上连通的,若对每个最小割集C,G-C 有孤立点.G 称为超连通的,若对每个最小割集C,G-C恰有两个连通分支,且其中之一为孤立点.本文刻画了上连通或超连通六次点传递图.     

单圈图最小特征值的Sharp下界

设G是一个具有n个顶点的简单图，λn(G)为图G的最小特征值，而单圈图就是其边数等于点数的连通图，本文给出了单圈图最小特征值的一个Sharp下界，并同时给出达到这个下界的极图。     

2-连通P3-支配图的可迹性

令G是n阶2-连通P3-支配图,本文证明了如果G满足2N C≥n-2,则G是可迹的.