三圈图的极小广义和连通指数

图的广义和连通指数作为新提出的一类分子拓扑指数, 在QSPR/QSAR 中有很大的应用价值. 树图、单圈图和双圈图的极值问题已取得很多结果, 而三圈图相关问题的研究较为复杂. 限制 - 1\leqslant \alpha < 0, 对三圈图的广义和连通指数进行了研究. 通过对三圈图的分析, 构造了一种图的变换, 指出在三圈图中广义和连通指 数的极小值必由其中的七种类型图取得. 然后通过悬挂边的变换, 最终得到三圈图广义和连通指 数的极小值并刻画了唯一的极图.     

4p阶三度点传递图

一个图称为点传递图或对称图如果它的自同构群分别在点集或点集有序对上传递.设P为素数,给出了4p阶连通三度点传递图分类(徐明曜等在[Chin.Ann.Math.,2004,25B(4):545-554]中分类了4p阶连通三度对称图).确定了4p阶互不同构的连通三度点传递图的个数f(4p);当P=2,3,5,7时,f(4p)分别为2,4,8,6;当P≥11且4|(p-1)时,f(4p)=5+p-3/2,当P≥11且4|(p-1)时,f(4p)=3+p-3/2.     

网络连通性的最优化

简述了极大边连通图和超边连通图;限制边连通度、极大限制边连通图和超限制边连通图的研究进展.     

广义友谊图乘积上的Graham pebbling猜想

连通图G的pebbling数f(G)是最小的正整数n,使得不管n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把一个pebble移到图G的任意一个顶点上.Graham猜测对于任意的连通图G和H有f(G×H)≤f(G)f(H).文中证明了当H为友谊图或广义友谊图,G是一个具有2-pebbling性质的图时,Graham猜想成立.作为一个推论,文中也证明了当G和H是友谊图或广义友谊图时,Graham猜想成立.     

3—连通局部连通无爪图是泛连通图

本文证明了若G是连通、局部连通的无爪图,则G是泛连通图的充要条件为G是3-连通图.这意味着H.J.Broersma和H.J.Veldman猜想成立.     

点可迁图的限制边连通性

3限制边割是连通图的一个边割, 它将此图分离成阶不小于3的连通分支. 图G的最小3限制边割所含的边数称为此图的3限制边连通度, 记作λ\-3(G). 它以图G的3阶连通点导出 子图的余边界的最小基数ξ_3(G)为上界. 如果λ_3(G)=ξ_3(G), 则称图G是极大3限制边连通的 . 已知在某种程度上,3限制边连通度较大的网络有较好的可靠性. 作者在文中证明: 如果k正则连通点可迁图的 围长至少是5, 那么它是是极大3限制边连通的.     

关于给定控制数的连通二部图的极大图的刻画

本文研究了给定控制数的连通二部图的极大图的结构问题.利用分类讨论思想和数学归纳法,刻画了控制数等于3和大于等于4这两类边数达到极值时的连通二部图.本文所得结果可用于进一步研究给定全控制数的连通二部图的极大图问题.     

多部竞赛图中包含某条弧的圈

多部竞赛图或n部竞赛图是指一个完全n部无向图的定向图.2007年Volkmann证明了每个强连通的n部竞赛图(n≥3)至少存在一条弧它包含在从3到n的每个长度的圈中.在此基础上给出了强连通n部竞赛图中存在一条弧它包含在从3到n+1的每个长度的圈中的一个充分条件,并举例说明该条件在某种意义上的最佳可能性.     

K1,4-受限图的路可扩性

图G中同构于K1,p的子图叫G的p-爪(p3).如果G中任意一个p-爪中1度顶点之间边的数目p-2,则称G为K1,p-受限图,它是无爪图(p=3时)的推广.本文证明了:连通、局部3-连通的K1,4-受限图是路可扩的.     

P3-支配图哈密尔顿性的两个充分条件

在文献[3]中介绍了一个新的图类-P3-支配图.这个图类包含所有的拟无爪图,因此也包含所有的无爪图.在本文中,我们证明了每一个点数至少是3的三角形连通的P3-支配图是哈密尔顿的,但有一个例外图K1,1,3.同时,我们也证明了k-连通的(k≥2)的P3-支配图是哈密尔顿的,如果an(G)≤k,但有两个例外图K1,1,3 and K2,3.     

上连通和超连通三次点传递图(英)

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

周长为3的m限制边割连通图

如果连通图的G存在边割S,使得G-S的每一个连通分支都含有至少m个顶点,则称图G是m限制边连通的.本文刻画了周长为3的m限制边连通图.     

非正规 Cayley 图的两个充分条件及其应用

群G的Cayley图Cay(G, S)称为是正规的, 如果G的右正则表示R(G)在Cay(G, S)的全自同构群中正规. 给出了非正规 Cayley图的两个充分条件. 应用该结果, 构造了5个连通非正规Cayley图的无限类, 并决定了A₅的所有连通5度非正规 Cayley图,从而推广了徐明曜和徐尚进关于A₅的连通3、4度Cayley图正规性结果. 此外, 决定了A₅的所有连通5度非CI Cayley图.     

3-连通(X,Y)-free图的Hamiltonian-连通性

一个图G称为(X,Y)-free图,如果G不含同构于子图X和Y的导出子图.本文证明了X=K_(1,3)、Y∈{D,W,B}的3-连通(X,Y)-free图是Hamiltonian-连通的.     

平方图的可圈性

连通图的幂图的可圈性研究在结构图论中具有十分重要的意义.论文主要解决了Klostermeyer在文献[2]提出的一个开放性问题,至少五个顶点的3连通图的平方图是一类可圈图.     

无限循环图的超边连通性(英文)

本文证明了 ,在一切具有有限跃度序列的无限循环图中 ,只有C( 1 ) ,C( 1 ,2 )和C( 1 ,2 ,3)不是超边连通的 ,而且C( 1 )和C( 1 ,2 )是其中仅有的两个非最大边连通图 .     

连通的K_{n}-残差图

m-K_{n}-残差图是由P. Erd\"{o}s, F. Harary和M. Klawe等人提出的, 当m=1时, 他们证明了当n\neq1,2,3,4时, K_{n+1}\timesK_{2}是唯一的具有最小阶的连通的K_{n}- 残差图. 首先得到了m-K_{n}-残差图的重要性质, 同时证明了当n=1,2,3,4时, 连通K_{n}-残差图的最小阶和极图, 其中当n=1,2时得到唯一极图; 当n=3,4时, 证明了恰有两个不同构的极图, 从而彻底解决连通的K_{n}-残差图的最小阶和极图问题. 最后证明了当n\neq1,2,3,4时, K_{n+1}\timesK_{2}是唯一的具有最小阶的连通的K_{n}-残差图.     

图的3限制性边割

3限制性边割将连通图分离成不连通图，使其各连通分支含有至少3个顶点．含3限制性边割的图在本文中得到刻划．     

关于图的余树的奇连通分支数的内插定理

本文研究了连通图的余树的奇连通分支数与其可定向嵌入的关系.我们先给出了关于连通图的余树的奇连通分支数的内插定理.作为其应用,我们推广了Xuong和刘彦佩关于图的最大亏格的计算公式,并且证明了如下结果:任意一个连通图G一定满足下列条件之一: (a)对于任意的满足γ(G)≤g≤γM(G)整数g,只要图G嵌入到可定向曲面Sg上,就存在支撑树T,使g-1/2β(G)-ω(T)),其中,γ(G)与γM(G)分别是图G的最小和最大亏格,β(G)与ω(T)分别是图G的Betti数和由T确定的余树的奇连通分支数; (b)对连通图G的任意一个支撑树T,G可以嵌入某个可定向曲面上使其恰好有ω(T) 1个面.特别地,我们给出了所有非平面的3-正则的Hamilton图G所嵌入的可定向曲面的亏格的计算公式.     

无K1,r图中的哈密顿圈（英文）

本文借助对图的本质独立集和图的部分平方图的独立集的研究，对于K1,r图中哈密顿圈的存在性给出了八个充分条件。我们将利用T－插点技术对这八个充分条件给出统一的证明，本文的结果从本质上改进了C－Q.Zhang于1988年利用次形条件给出的k-连通无爪图是哈密顿图的次型充分条件，同时。G.Chen和R.H.Schelp在1995年利用次型条件给出的关于k-连通无K1，4图是哈密顿图的充分条件也被我们的结果改进并推广到无K1,r图。