雄鹰图 新竹图

雄鹰图新竹图雄鹰图 新竹图@王一琴 @罗金远     

舵轮图都是强协调图

一个有e条边的简单图G称为是强协调的,若有V(G)到{0,1,…,e-1}的单射h,使导出映射h~*:h~*(uv)=h(u)+h(v)是由E(G)到{1,2,…,e}的一个双射。舵轮图H_n是由含n个顶点的圈C_n内添加一个与C_n的每个顶点都相邻的顶点,且再在C_n的每个顶点上都添上一条悬挂边而得到的图。本文中证明了,所有舵轮图都是强协调图,因而回答了[2]中一个open问题。     

图角及图变换

运用图角,给出简单图的补图的特征多项式,并研究把一些图作适当变换后,它的特征多项式的变化情况．     

变换图的张量积图

文章定义了变换图的张量积图.为了研究其内在结构特征,给出了张量积图的边数不等于0的充分必要条件,并证明了两个变换图的顶点数乘积等于其张量积图的顶点数,两个变换图边数的较大者等于其张量积图的边数,两个变换图直径的较大者等于其张量积图的直径.     

正合图、拉回图、推出图的性质

拉回、推出是范畴论中的重要概念,本文引进与拉回图推出图有关的正合图概念,探讨了这三种图的性质和联系。     

眼镜图的谱刻图

只有与G同构的图才有相同的谱,则称图G是谱唯一确定的.眼镜图是在圈Cp和圈Cq的任意一个顶点之间加一条边构成的图,记为g(P,q).证明了眼镜图是谱唯一确定的.     

卡诺图的一图多用

本文从不同角度分析阐述了卡诺图在《数字逻辑》中的各种应用     

组合竞赛图的控制图

竞赛图是完全无向图的定向图,具有任意两个顶点之间有且仅有一条弧的性质。竞赛图的控制图和竞争图有比较紧密的联系,对竞赛图的控制图的研究由来已久,并在生物竞争图的结构刻画上起到了重要的作用。设T是c个顶点的竞赛图,S_i(i=1,2,…),c分别是竞赛图,那么称D=T[S_1,S_2,…,S_c]为T的组合竞赛图。通过研究组合竞赛图的控制图的性质和结构,对原有针对竞赛图的定理进行扩充,针对如何求解竞赛图的控制图,推导并求解组合竞赛图的控制图,并给出相应算法。     

图的割集与图代数

唐守文、赵春来定义了图代数并作了一系列研究,其中一个定理是用图代数的理想来刻划图的s—割集的存在条件,但他们的证明相当繁琐,这里我们给出一个简单的证明并由此得出割集S的明确作法     

扩充竞赛图的控制图

设D=(V,A)是一个有向图,对x,y∈V(D),记O(x)是x控制的顶点的集合,如果O(x)∪O(y)∪{x,y}=V(D),则称x和y控制D。有向图D的控制图记为dom(D),它是一个无向图,顶点集是V(D),且对x,y∈V(D),xy是dom(D)的一条边当且仅当x和y控制D。文章研究扩充竞赛图的控制图,并给出了求解扩充竞赛图的控制图的一个算法。     

完全偶图的定向图

完全偶图是具有二分类（X,Y）的简单偶图，其中X的每个顶点与Y的每个顶点相连，若｜X｜=m,｜Y｜=n，则这样的图记为K_m,n。本文主要研究了Kn,n的定向图。证明了如下结论：对于非负整数a和b，若存在满足每个顶点的入度是a或者是b的一个Kn,n的定向图，则存在非负整数s和t满足方程s+t=2n和as+bt=n2。进一步，对于满足特定条件的非负整数a，b和n，存在K_n,n的定向图使得每个顶点的入度非a即b。     

Grotzsch图的匹配等价图

文章研究了Grotzsch图的一些性质,以及它的匹配等价图.     

齿轮图都是调和图

称一个含q条边的简单图G是一个调和图,若存在单射h:v(G)→{0,1,…q-1}使得导出映射h~*:E(G)→{0,1,…,q-1},h~*(uv)≡h(u)+h(v)(modq)是一个双射。这里u,v∈V(G),uv∈E(G)。在轮W_n的轮圈C_n上每两个相邻点之间加入一顶点所得之图称为齿轮图(?)_n。本文将证明,所有齿轮图(?)_n都是调和图。从而回答了[4]中提出了一个open问题。     

贝壳图是整和图

整和图理论研究的是图的一种标号方法,从实用的角度看,整和图标号可用作图的压缩表示,即表示图的数据结构,可作为图的一种定义及存储方式.笔者采用顺序标号法分别给出贝壳图MS{4n}、MS{5n}的整和标号,从而进一步推广并证明了所有贝壳图MS{mn}(m≥3,n≥2)都是整和图.     

轮图和联图对应图构形的特征多项式

利用构形中的“删除 限制”方法, 通过考察n-圈和n-路图, 分别给出轮图和两条路的联图对应图构形的特征多项式.     

特定的竞赛图是哈密顿图

证明了命题“竞赛图D=(V,E),顶点的个数|V|=n为奇数,对Vv∈V,d^ (v)=d^-(v)=n-1/2竞赛图是哈密顿图。”     

轮图中间图的pebbling数

图G的一个pebbling移动是从一个顶点移走2个pebble,而把其中的一个移到与其相邻的一个顶点上.图G的pebbling数f(G)是最小的正整数n,使得不管n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把一个pebble移到图G的任意一个顶点上.文章研究轮图中间图的pebbling数.     

图的形成原理与图的模式及图的本质

本文沿着图的形成原理这个切入点,运用正确的思维方法和比较证明方法,对四色猜想命题中的图的面与面之间的关系、图的模式、图的本质进行了论证,得出了＂图的形成原理是组合形成整体或整体被分划的过程＂、＂图的面与面之间的关系是组合关系＂、＂图的模式是Cn2组合模式＂、＂图的Cn2组合模式就是图的本质＂的结论。这些结论是本人在研究四色猜想命题方面的重要成果,也是＂张尔光组合说＂的重要组成部分。     

系列并行图,4阶完全图与小树宽图

给出了树宽≤2的图也就是系列并行图的几个等价刻画。证明了对有限图G(可以有环有重边)以下四断言彼此等价:(1)G是系列并行图,(2)G的任一个minor至少有一个点的度≤2;(3)G不以4阶完全图为minor;(4)G无子图同胚于4阶完全图。