2m+1个顶点的m正则图中哈密尔顿回路数

如果无向图G中的每两个不同的顶点u和v间都存在一个哈密尔顿u-v路,那么,图G被称做哈密尔顿连通图。文献〔1〕中证明,所有2m+1个顶点的m正则图都是哈密尔顿连通图,而且至少包含m/2个哈密尔顿回路。本文证明,每个2nm+1个顶点的m正则图至少包含m-1个哈密尔顿回路。

边色数临界图

本文定义了一类x′-临界图。如果对每条边e∈G都有x′(G-e)<x′(G),别称图G是x′-临界图。k-x′-临界图是k-边-可着色而且临界的图。本文首先证明每个图都包含x′-临界图,△-x′-临界图是k_1+△k_1,其次证明了(△+1)-x′-临界图的几个性质。

4部完全图的全着色研究

本文对所有4部完全图证实了全着色猜想。