临界极大外平面图

给出了临界极大外平面图以及最大度临界极大外平面图的定义，并讨论了它们的性质，为研究极大外平面图的四染色提供了一种新方法。     

平面图的4—着色的简单布尔方程表示

如果一个无环平面图G至多有一个非三角形的面,则称G为准极大平面图（near-trian-gulation)本给出了极大平面图和准极大平面图4－着色的一类布尔方程表示式,该布尔方程所含变元较少,结构简单,具有良好的递归性质,为利用计算机寻找给定平面图的4－着色提供了很好的算法。     

n阶极大外平面图的构造法

图的同构的判定是图论研究中的重要课题之一,非同构的极大外平面图的计数问题尚未解决.提出一种判定图同构的方法,其原理是赋予每个无标号极大外平面图一个n×(n-3)阶0-1矩阵,证明了矩阵与极大外平面图一一对应,矩阵相同的图彼此同构.构造所有可能的n阶极大外平面图,并用上述方法除去其中同构者,所有n阶无标号极大外平面图被不重不漏地构造出来,同时得到其总个数,解决了有关极大外平面图同构与计数问题.     

极大外平面图谱半径的上界

每个点都在图的一个面的边界上的平面图叫外平面图,具有最大边数的外平面图叫极大外平面图.首先给出了一类极大外平面图的特征多项式的表达式,由此给出了对任意n≥4都成立的极大外平面图谱半径的一个上界,并证明了当图的点数增大时,这个上界与谱半径是等价的无穷大量.     

极大平面图的面色数

极大平面图 G的面色数不超过 4,且其为 4当且仅当G为 4阶完全图     

两个同构型判定问题的一种可行解决方案

本文对两个同构型判定问题提出了相应的可操作的检验、判定方案。一个是极大平面图有没有非平凡的自同构置换，另一个是两个极大平面图是否同构。     

极大平面图对偶二色子图结构特性树

本文在论文[1]的基础上给出极大平面图的另外一种商图,即极大平面图对偶二色子图结构特性图.证明极大平面图对偶二色于图特性图是树,并给出它的若干性质.     

一类极大平面图4-着色布尔方程组

对极大平面图的4-着色布尔方程组F1d1(x1,x2,…,xn)=1 F2d2(x1,x2,…,xn)=1……Fndn(x1,x2,…,xn)=1进行研究,得到了该布尔方程组的5条性质,并且给出了求极大平面图4-着色全部解的一个算法.     

关于高度极大外平面图的4染色

从最大度的角度讨论两大极大外平面图的公共４染色，证明了当Ｇ是以ｒ个顶点的圈Ｑｒ为标定界环的极大外平面图且△（Ｇ）≥ｒ－２，Ｇ′是以Ｑｒ为标定界环的任一极大外平面图时，Ｇ和Ｇ′有公共４染色，从而证明了四色定理的等价例题在给定条件下成立。     

△≥r—2的极大外平面图的4染色

从最大度的角度讨论极大外平面图的染色,证明了以ｒ个顶点在圈Ｑｒ为标定界环的最大度△≥ｒ－２的任意两个极大外平肌图都有公共４染色。     

非本原强正则图的充分条件

设 G 是一个(n,k,α,c)-强正则图,(n,■,■,■)是它的补图。若它们的参数满足下列条件之一:1)k,n—1互素;2)k,■互素;3)α=k—1,那么 G 是非本原的。G 是非本原的当且仅当■=■或■=0.     

奇围长为r的对称图的指数集

令E_(r,n) 表示夸围长为r的n阶对称图的指数集。本文证明了:E_(1,n)={1,2,…,2n-2}\x_1,当3≤r≤n时,E_(r,n)={r一1,r,…,2n-r-1}\x_r 其中x_i为[2[n\2]-i+2,2n-i-1]中的奇数,i=1,r.并刻划了指数为2n-r-1的奇围长为r的对称图的特征。     

δ>2极大平面二分图间的关系

本文讨论δ>2极大平面二分图之间的关系,证明了 B_(mn)每一图可由其任一图经改边得到.     

迹为零的本原（0，1）－矩阵的指数集

设Ｅｎ是ｎ阶本原（０，１）－矩阵的本原指数集，ＺＴＥｎ表示迹为零的ｎ阶本原（０，１）－矩阵的指数集。当ｎ≥４时，ＺＴＥｎ＝Ｅｎ＼｛１｝；ＺＴＥ１＝ＺＴＥ２＝φ；ＺＴＥ３＝｛２，４，５｝。     

给定指数的本原有向图的哈密尔顿性质<英>

本文研究了给定指数n+s(n-2)的本原有向图的哈密尔顿性质,并得到如下结果:(1)设D是围长为s≥2,指数为n+s(n-2)的n阶本原有向图,如果D中有一个r-圈,使降(r,s)=1.则D是哈密尔顿的。(2)设D是包含环,指数为2n-2的n阶本原有向图,则D是哈密尔顿的充要条件是d(D)=n-2,这里d(D)是使γ(n,v)=γ(D)的n到v的最大距离。     

用Tensor乘积法构造整谱有向图

通过研究Tensor乘积图与其谱之间的关系,得到Tensor乘积图是整谱图的条件,并由此获得了构造新的整谱图的方法,找到了一些新的整谱有向图.     

本原半环的稠密性及Kaplansky定理

若半环Ｓ有忠实既约的Ｓ－半模Ｍ，叫Ｓ为本原半环．我们证明了本原半环具有稠密性，然后在此基础上证明了所谓的Ｋａｐｌａｎｓｋｙ定理，即ＰＩ－本原半环是单的，在其中心上是有限维的．     

平面三次图哈米尔顿性的一个充要条件

本文证明平面三次图Dg有哈米尔顿圈的充分必要条件是与之对偶的极大平面图g有树树型四着色．即Dg的对偶极大平面图g有四着色C，该四着色的某组对偶二色子图Gk的两个分支都是树．据此得到求出图Dg全部哈米尔顿圈的算法，该方法已经成功处理了批量例图．     

Heawood反例图的全部四着色

本文首次报告了Heawood反例图的全部四着色.它可以用一个树林来描述.树林的每个分支是一棵四着色树.四着色树是一个根树.根节点Cr是Heawood反例图的一个四着色.根树其它节点都是经过一个或多个二色变换从Cr变来的.Heawood反例图有37个四着色树.其中有35个偶四色树(包括24个是仅有根结点的退化型四色树),2个奇四色树.偶四着色总计112,奇四着色总计144,全部四着色总共256个.这些结果都是用Maple编程得到的.     

图的谱半径的界

我们定义简单图G的点的邻度为该点的邻点的度之和。本文的主要结果是:若r是连通简单(p,q)-图G的谱半径,则有■其中δ、△、■和■分别是图G的最小度、最大度、最小邻度和最大邻度。