n阶三圈图的补图的谱半径

三圈图是边数等于顶点数加2的简单连通图.在所有n阶三圈图的补图中,哪一个的谱半径最大?文中给出了n阶三圈图的补图的谱半径的上界,并刻画了唯一的达到该上界的图.     

图与补图全独立数间的关系

对图G(V,E),V∪E中既不相邻、又不相关联的最大元素个数,称为G的全独立数,并简记为α_T(G)。本文研究了图和补图全独立数之间的关系,得到α_T(G) α_T(G~C)≤「3y 1/2」。其中y=|V(G)|,G~C是G的补图,「x」为不大于x的最大整数,且界可达。     

具有八个节点的自补图

In this note we deduce that there are exactly 10 self complement graphs on 8 vertices (G=G), which is characterized in the sort of degree sequences . It is a correction to the assertation made by Harary ( [ 1 ]) .     

关于图与补图的带宽的一个简单证明

关于图与补图的带宽,P.Z.Chinn,F.R.K.Chung,P.Erd?s和R.L.Graham证明了B(G)+B(G)≥n-2.本文给出一个简单证明.     

图论与复杂网络

近10年来迅猛发展起来的复杂网络理论为研究复杂性与复杂系统科学提供了一个重要支撑点,它高度概括了复杂系统的重要特征,无论是在理论还是在应用方面都具有很强的生命力,而且在各个方面都得到了很大发展. 重点讨论图论在复杂网络中的应用, 特别是代数图论在复杂网络同步问题中的应用. 首先给出一些图的最小非零与最大特征值以及同步能力的估计, 并且讨论了子图与图特征向量在同步能力估计中的作用. 其次以两个简单图指出同步能力与网络结构参数的关系复杂, 并给出补图与加边对同步研究的意义, 然后给出图运算在复杂网络同步中的作用. 最后从图论与控制理论角度展望了复杂网络领域未来可能的发展方向.     

树的Nordhaus-Gaddum类型谱半径的排序

给出了n阶树的Nordhaus-Gaddum类型谱半径即图及其补图的谱半径之和的可达上界:ρ(T) ρ(Tc)≤■ n-2,等号成立当且仅当T K1,n-1,其中Tc为T的补图,K1,n-1为n阶星图.同时证明了对于n阶双星图S(a,b)的Nordhaus-Gaddum类型谱半径随a的值单调上升,其中[n-1/2]≤a≤n-3.     

关于全图补图的完美匹配

G是一个简单图,变换图G---是G的全图的补图.证明了对于给定的一个图G,G K1 K2,G---有一个完美匹配的充要条件是V(G) E(G)是偶数.     

代数构造及在Ramsey理论中的应用

这篇文章在伽罗瓦域上的代数构造和关于一些特定类型图的Ramsey数之间建立了一个关系. 研究了关于伽罗瓦域上的代数构造的方程及方程组的解. 我们得到了一些关于二部图的Ramsey数的新的下界和上界.     

图与其补图谱半径之间关系的注记

给出在一般情形和某些限制条件下图及其补图的谱半径的和与积的上界，改进了文［１］的结果。     

色多项式的Akiyama—Harary问题

J.Akiyama和F.Harary提出:是否存在非自补图G,使得G与其补图有相同的色多项式,本文给出一个肯定的回答,并证明了:这样的平面图G仅存在有限多个。