关于部分标定简单图的数目

本文讨论部分标定简单图的数目,首先介绍了计算标定简单图的公式,然后确定了当顶点个数为3时的标定简单图的数目为8个。主要证明了当顶点个数为4时的标定简单图的计数以及所有画法,并用数学方法证明了它的数目的精确值为64。最后也给出当顶点个数为4时,非标定简单图的数目为11个以及全部画法。近百年来,国内外很多学者都对这一问题进行了研究。由于所涉及的画法较多并且证明过程较为复杂,国内外关于此领域的研究进展缓慢。相比较而言,本文给出了四个顶点的标定简单图的所有画法,并采用度序列的方法更简洁直观,更具创新性。

一类可传递分解图的交叉数

图的交叉数是拓扑图论中重要的一个分支,国内外诸多学者对图的交叉数这一问题进行广泛的关注和深入的研究,Garey和Johnson证明了计算图的交叉数是NP-完全问题。本文令cr(G)表示图G的交叉数,主要利用弱积图Cn × K3的一个传递分解{H1,H2,...Hn}对其交叉数进行研究。首先构造了六边形图C2k × K3交叉数较少的画法,给出交叉数的上界,然后采用数学归纳法和反证法,将C2k × K3的边集分成边不相交的2k组,讨论所有可能情况,从而证得cr(C2k × K3) = 4k,k ≥ 3。