关于Hamilton图的一点注记

通过类似于对一可平面图求生成树个数的方法,得到一个关于Hamilton图的Hamilton圈的个数的等式。并讨论了一类特殊的平面图。     

三正则平面图与平面三角剖分图

探讨三正则平面图的路与平面三角剖分图 Hamilton圈的关系 ,给出平面三角剖分图 Hamilton圈的一个充分条件及算法     

平面图与面的并区域

Sachs,Kozyrev和Grinbery指出平面图具有Hamilton圈的一个必要条件是2,其中φi和φ'i分别为Hamilton圈内、外应为i的面数．本文探讨面的度相等的平面图的面数,面并成顶点在边界上的连通区域与Hamilton圈.     

面的并区域与三正则图的Ham ilton圈

Sachs. Kozyrev和 Grinbery指出了平面图具有 Hamilton圈的一个必要条件是 ∑ni=3 ( i-2 )i=∑ni=3 ( i-2 ) ′i=n-2 ,其中 i 和 ′i 分别为 Hamilton圈内 ,外度为 i的面数 ,在这个必要条件的基础上 ,给出了三正则平面图 Hamilton圈的一个算法     

关于最大度为 7 的平面图全染色的一个注记

给最大度为Δ的图进行全染色至少要用Δ+1种颜色.全染色猜想断言每个图都是(Δ+2)-全可染的.但即使对于平面图,全染色猜想依然未得到证实.在该研究方向已证明满足下述条件之一的最大度为Δ的平面图是(Δ+1)-全可染的:1)Δ≥9;2)Δ=8且不含相邻三角形.证明了最大度为7且不含带弦4-圈和带弦5-圈的平面图是8-全可染的.该结果进一步拓展了(Δ+1)-全可染平面图类.     

距离无爪图的Hamilton性

距离无爪图类属于无爪图类。所谓距离无爪图是对图中的每一个顶点,其距离为的邻域的独立数均不超过3的图.F.BruceShephed已证明:若G是距离无爪图且G是2─连通的,则G有Hamilton路;若G是距离无爪图且G是3─连通的,则G有Hamilton圈.本文在此基础上,定义了一种新的禁用子图──网全爪,首先证明了2-连通的、无网的距离无爪图有Hamilton圈.又证明了2-连通的有网、无网全爪的距离无爪图有Hamilton圈.     

最大度为△的平面图的（△＋2）-全可染性

研究了A=6的平面图的（△＋2）一全可染性,证明了△=6且3-圈和6-圈不相邻的平面图是8-全可染的．这一结果进一步扩展了（△＋2）-全可染（平面图）图类．     

平面图与对偶原理

该文利用对偶原理创造性地解决了平面图、连通图及对偶图之间的相互关系问题,纠正了长期以来对于平面图及其同构的错误认识,指出平面图必为连通图,平面图本质上是画在同一平面上的顶点、边、面均不相交的连通图.两个平面图的同构指这两个平面图的顶点、边、面之间均有一一对应关系.面是平面图区别于非平面图的本质特征.同构的平面图的对偶图必同构,事实上,平面图的对偶图是唯一的.任意一个平面图都伴有一个隐图,而该隐图实质上是该平面图的对偶图,该隐图可(根据对偶原理)通过 D-过程画出.平面图与其对偶图互为对偶.显平面图与其隐对偶图合称为相伴对偶图.     

平面图与对偶原理

该文利用对偶原理创造性地解决了平面图、连通图及对偶图之间的相互关系问题,纠正了长期以来对于平面图及其同构的错误认识,指出平面图必为连通图,平面图本质上是画在同一平面上的顶点、边、面均不相交的连通图。两个平面图的同构指这两个平面图的顶点、边、面之间均有一一对应关系。面是平面图区别于非平面图的本质特征。同构的平面图的对偶图必同构,事实上,平面图的对偶图是唯一的。任意一个平面图都伴有一个隐图,而该隐图实质上是该平面图的对偶图,该隐图可(根据对偶原理)通过D—过程画出。平面图与其对偶图互为对偶。显平面图与其隐对偶图合称为相伴对偶图。     

最大度为6不含相交三角形和4-圈的平面图的全染色

全染色是对图G的顶点和边同时进行正常染色,至少要用Δ+1个色才能对图G进行正常全染色.运用权转移的方法,证明了最大度为6不含相交三角形和4-圈的简单平面图是7全可染的.     

图的谱半径和Hamilton性

从图G的闭包理论角度去研究图的Hamilton性。利用图的补图谱半径的界，讨论了Hamilton图存在的谱条件，证明了n阶图G，如果它的补图的谱半径小于或等于（n-3）的算术平方根，则G是Hamilton图。     

2-坚韧图是分数Hamiltonian

分数Hamilton图是比Hamilton图更广泛的图类.论文借用线性规划的知识给出了判定分数Hamilton图的新的充分必要条件,并利用新的充分必要条件证明了任意2-坚韧图是分数Hamiltonian.     

Heawood图的一对对偶树的分解和4-着色

阐明了任意平图的4-着色的主要思路,给出了对偶树的定义。对偶图中的一对对偶树与对偶图的Hamilton路径相互依存,提出了任意平图的4-着色的方法步骤。得到利用上述方法得到的一对对偶树及具有的性质。介绍了Heawood图的由来和基本特点、Heawood图的4-着色的2种方法步骤,通过对偶图的2个区域的划分,实施了Heawood图的4-着色,借助于Heawood图的对偶图的Hamilton路径的分解构造了2棵对偶树。借助于此方法所得的Heawood图的25个顶点的4-着色方案达到236个,从而使Kempe的4-cc猜想"证明"中的漏洞得到弥补。     

一类无三角正则图的性质

图为无三角正则图,它满足不相邻的顶点恰有两个公共相邻顶点.先从代数的角度去研究它的特征值,得到了它的顶点个数只能取一些特殊的整数,然后证明了其点连通度与边连通度相等,而且存在完美匹配,最后猜想:(1)x(G)=x'(G)=k;(2)图G是Hamilton图.     

哈密尔顿图教学中的几个问题

针对离散数学课程教学面临的一些问题,以哈密尔顿图教学内容为例,讨论了教学中的三个问题,以达到理解教学内容、引发思考、提高自主探索能力的目的。     

关于3-正则4-可序图无限类的构造

Lenhard Ng(1997)给出k-可序(k-ordered)哈密尔顿图的定义,并证明了每一个(k 1)-Hamilton-连通图都是k-可序哈密尔顿图．Faudree J R(2000)将k-可序哈密尔顿图的定义改进为k-可序图．根据Lenhard Ng提出的开问题：是否存在3-正则4-可序哈密尔顿图的无限类,以及Faudree J R给出的可序图的定义．构造了3-正则4-可序图的无限类．     

上可嵌入图与次上可嵌入图的线性荫度

通过度再分配的方法研究上可嵌入图与次上可嵌入图的线性荫度,证明了最大度△不小于(4-3ε)~(1/3)且欧拉示性数ε≤0的上可嵌入图其线性荫度为「△/2」.对于次上可嵌入图,如果最大度△≥(4-3ε)~(1/3)且ε≤0,则其线性荫度为「△/2」.改进了文献[1]中最大度的的界.作为应用证明了双环面上的三角剖分图的线性荫度.     

一个Hamilton图形充分性的研究

讨论了特殊的 4k(k >1)个结点的简单图中存在Hamilton回路的充分性 ,并由此提出 :具有 4k个结点的 (2k - 1)正则简单图都是Hamilton图 .     

三次图的完全扩容图的连通度

目的研究三次图的完全扩容图的连通度。方法利用反证法。结果与结论3-连通三次图的完全扩容图也是3-连通三次图。