构造极大平面图的三种方法

对极大平面图的构成方法做了进一步的研究,提出了三种构成方法：规范的“加点法”与“删步法”以及非规范的“任意法”,并对三种构成方法进行了比较分析。同时对同阶非同构极大平面图的计数问题进行了理论分析。以命题形式给出了８个结论,这些结论对研究极大平面图的点着色问题有其理论与应用价值。     

构造极大平面图的圈加点法

“四色猜想”提出将近１５０年了,但至今尚未解决。经数学家们研制“四色猜想”问题等价于平面图是可４着色。若能证明极大平面图可４着色,则“四色猜想”问题即迎刃而解。研究极大平面图的着色问题,就涉及到极大平面图的结构特点及其构造方法,因此,研究构造极大平面图的方法就是必要的了。通过对极大平面图的结构研究,每个结点的邻接结点均构成圈,由此提出了构造极大平面图的“图加点法”。该法简单规范,可无遗漏地构造任意     

同构极大平面图研究

从作者前文《极大平面图的构成算法》中的“极大平面图充分必要条件定理”为基础,经分析研究推论出“极大平面图中任意结点的邻接眯必构成圈”。进而提出了“极大平面图同构的充分必要条件定理”并给予证明,最后,归纳出“求任意阶所有的非同构极大平面图的算法”,从而为研究极大平面图的着色问题提供基础。     

极大平面图的构成算法

采用常规教学方法研究平面图的“四色问题”，行对极大平面图的结构进行分析研究也许是必要的。从证明极大平面图的充分必要条件定理出发，得到求作任意阶极大平面图的方法。     

极大平面图的色数研究

以极大平面图的结构研究为基础,采用常规的数学推理方法研究极大平面图的点色数问题。运用“并行（或平行）数学归纳法”证明了由“面内加点”或“边上加点”方法所构造的任意阶极大平面图是可四着色的。     

关于(4,6)-正则极大平面图的构造

当图的顶点数n>12时不存在正则极大平面图.文献[2]提出了(r,k)-正则极大平面图的概念,并讨论了(5,6)-正则极大平面图的存在性.本文讨论了(4,6)-正则极大平面图,得到了(4,6)-正则极大平面图的存在条件及构造方法.     

几乎外平面图的边染色

若图G存在边e使G-e为外平面图，则称G为几乎外平面图．本文证明了，连通几乎外平面图G是第二类的当且仅当G是奇圈或△(G)=3且G有一个2-连通子图G′含有唯一的2-度点．同时，Fiorni关于外平面图边色数的结论得以推广．     

几乎外平面图的边染色

若图G存在边e使G -e为外平面图 ,则称G为几乎外平面图 .本文证明了 ,连通几乎外平面图G是第二类的当且仅当G是奇圈或Δ(G) =3且G有一个 2 连通子图G′含有唯一的 2 度点 .同时 ,Fiorni关于外平面图边色数的结论得以推广 .     

关于Knight's Tour Problem的图论解法

通过分析欧拉所给出Knight’s Tour Problem的解法,结合哈密尔顿路和哈密尔顿圈的相关知识,得出其解法对应着二部图中的一条哈密尔顿圈.由此再充分利用8×8棋盘所对应的8×8表格的对称性及同格图的特性,对欧拉所给出的Knight’s Tour Problem的解法作了进一步的探讨,得出了以欧拉的解法为基础的以任一棋格为骑士周游起点的另外一系列解法.最后,把Knight’sTour Problem推广到m×n棋盘上,考虑到移动规则的特殊性,利用图论的相关知识,得到3×4,8×16和16×16棋盘上的Knight’s Tour Problem的解法,同时给出8m×8n(m>2,n>2)棋盘上Knight’s Tour Problem的猜想.     

一类四次正则图

近几年来很多作者讨论了多计算机系统中的稠密网络问题以及在图论中与此有关的(△,d)图问题。本文概述了这方面的一些成果并提出一类四次正则图(圈五——树形图)的构造方法并讨论了它的直经。     

探析同构图证明的新方法

同构图的证明一向按定义进行,较为繁琐且无规律性,现在通过将图的邻接矩阵化为一致的“标准型”,达到了证明两图同构的目的,归纳出一种证明两图同构的简便方法。     

求图的最小树的表上作业法

本文给出了求图的最小树的一个新算法,用它可以求出一个图的所有的支撑树。     

依赖于点的度数的一类图的能量下界

G为n阶简单图,其能量记为E(G),E(G)=sum from i=1 to n︱λi︱ ,其中λ1,λ2,…λn为图G的邻接矩阵的特征值.围绕最大度不大于3的n阶无四圈图,证明了其能量不小于n-1.讨论了一类能量大于阶数的图,并进一步得到一类超能图.     

极大平面图的色数研究(续)

以文献《极大平面图的色数研究》为基础,对“加点法”所遗漏的极大平面图进行再研究,证明了这些极大平面图也是四着色的。     

一类度极大的非哈密尔顿简单平衡二部图

证明了"任何非哈密尔顿的简单平衡二部图,它的不减度序列一定弱于一类图(即度极大的非哈密尔顿简单平衡二部图)中的某个图bm,n的度序列".本文给出了这一类图bm,n的结构.     

关于无爪图的哈密尔顿性的一个充分条件

设G是阶为n,连通度为k(k≥2）的无K1,k 2图。本文证明了：对于任意2－独立集,S＝｛u,v,w｝,或者d(u) d(v) d(w)≥n k,或者S中存在x和y(x≠y),使得λxy≥min｛α^2xy,t^2xy 1｝,则Ｇ是哈密尔顿的。     

利用Polya定理计算图的计数

以Polya定理为理论基础，在不做图的情况下，通过计算38个顶点以下的不同构简单图的个数，并通过构造图的计数多项式，将13个顶点以下的各阶图按边数进行分类计数，从中发现了一个结论，并给出了证明．     

几种特殊图之间和的Cordial性

给出了路Pm、圈Cn、扇Fp和轮Wq4种图之间和的Cordial性，所得结果扩展了文献Eli（Gallian J A. A Dynamic Survey of Graph Labellings of Graphs. Electronic Journal of Combinatorics，2005（5）：DS6）的研究工作．