Some Results on Arithmetic and Balanced Graphs

首先考虑Ａｃｈａｒｙａ和Ｈｅｇｄｅ关于算术平衡图的三个猜想．其中一个已由他们证明，本文给出它和另一个猜想的简单证明，并指出第三个猜想在一般情形下是不对的，而在一个更强的条件下是正确的．然后讨论本文结果与已知结果之间的关系．     

关于正则图的道路双覆盖猜想

［１］汇集了１９９０年国际图论会议（丹麦）上所提出的２７个新的未解决的问题，其中第一个就是关于正则图的道路双覆盖猜想，Ａｄｒｉａｎ Ｂｏｎｄｙ等人利用Ｐｅｔｅｒｓｅｎ定理已证明：对于３－正则图猜想为真。本文证明了对于任意的ｍ－正则的完全图，猜想是成立的。     

平方根图

设G是一个简单图及顶点为u1，u2，…，uv，d(vi)是点vi的度，令^～d(G)={[d(u1)]的平方根，[d(u2)]的平方根，…，[d(uv)]的平方根}，称G是一个平方根图，如果^～d(G)是G的邻接矩阵的一个特征向量，猜想：一个连通图G是一个平方根图的充分必要条件是G是一个正则图或半正则图，这个猜想在本文中得到了证明。     

关于Powell的一个猜想

对于Ｐｏｗｅｌｌ提出的一个猜想，本文给出一个新的和简短的证明。     

关于Youself Alavi的一个问题

本文证明了文[1]提出的一个猜想。     

关于临界图的若干结果

Ｖｉｚｉｎｇ’ｓ猜想：ｎ阶Δ－临界图的边数ｍ满足ｍ≥（ｎΔ－ｎ＋３）／２。本文证明了当ｎΔ＝３时猜想也成立以及当５≤Δ〈ｎ／２，ｎΔ＝４时猜想也成立。同时给出了临界图的两个新的性质。     

一类具有生成闭迹的图

1987年，P．Paulraja在[2]中给出如下猜想：如果G是δ（G）≥3的2－连通图，且G的每条边均属于长为3或4的圈，则G有生成闭迹，同年P．A．Catlin在[3]中猜测上述的G还是可折迭的（Collapsible)，本文给出了这两个猜想的证明。     

关于HOVEY的一个猜想

证明了Ｈｏｖｅｙ在１９９１年的一篇文章中提出的一个猜想，并弥补了Ｈｏｖｅｙ在同一篇文章中一个定理证明中的漏洞．类比ｋ－忠实标号对图的调和标号的推广，优美标号做了进一步的推广。     

关于图谱半径的一个不等式

本文所提出关于图谱半径的一个猜想,并对某些特殊情况证明猜想成立.     

完全3部图的一类同构分解

本文构造性地证明，对于完全3部图 G（X，Y，Z；E），如果边数能被正整数t整除，且｜X｜, ｜Y｜和｜Z｜三个数之一也能被t整除，则完全3部图可分解为t个同构因子，从而证实了Harary “3部图猜想”的部分结论。     

临界图独立数的上界

1968年,Vizing猜想,对于n阶的△临界图G,其独立数a（G）≤n/2．利用著名的Vizing邻接引理和Fiorini不等式的证明方法,证明了如果临界图G的一个最大独立集中主顶点个数不超过1,则猜想成立,从而改进了Luo等的一个结果．     

Hayman猜想的简捷证明与相关的正规定则

本给出Ｈａｙｍａｎ的一个猜想的简捷证明，同时证明了一个相关的正规定则。     

关于Enomoto和Saito的猜想

1985年Enomoto和Saito提出了下面的猜想:每一个r-正则图G有一个〔k-1,k〕-因子使每个分支是一个正则图,1≤k≤r.Kano证明了,当r是奇数且02r/3时在某些情况下上述猜想成立.     

关于模算术的几个问题

提出了两类关于双重模的模算术的四个问题，并利用数论和代数学的方法，对其中的三个问题给予了否定的证明，对剩余的一个问题提出了一种猜想。     

涉及两个三角形的若干不等式

运用配方法证明了涉及两个三角形的两个Neuberg-Pedoe型不等式，并修正、证明了一个与N-P不等式相媲美的猜想，给出了三个N—P型不等式的简单证明．     

区间图和强弦图的全着色及最优算法

证明对于任意区间图和强弦图－全着色猜想成立，并且给出了区间图和强弦图的最优线性地，其算法复杂度仅为Ｏ（Ｖ＋Ｅ）。     

关于图存在三角形的一个充分条件

对图论中的Woodall关于结合数的一个猜想作了研究.证明若图G的结合数bind(G)≥6 √22/7,则图G包含三角形,同时还证明了:若bind(G)≥3/2,且δ(G)＞P(G),则Woodall猜想是正确的,从而改进了现有的某些结果.     

直积图的分数色数

有关直积图的色数,在图论中有Hedetniemi猜想,该猜想是建立在连通图的基础上,并且已证明该猜想对于一些特殊图是成立的.证明了对于连通的点传递图,Hedetniemi猜想在分数染色意义下也是成立的.     

连通、局部连通无爪图的K-Hamilton性质——Broersma和Veldman猜想的新证法

Broersma和Veldman提出了如下的猜想:连通、局部K-连通无爪图G是K-Hamilton图的充分必要条件为G是(K+2)连通的。本文证明了这个猜想是正确的。     

Fibonacci三角形的一个充要条件及应用

得到Fibonacci三角形关于二元四次丢番图方程的充要条件，作为一个应用，使用与文不同的方法，证明了Fibonacci三角形猜想当k=5时成立。