环面上格子图Cm×Cn的带宽

求一个图(Graph)——或一个对称矩陣——的带宽(Band width)是一个很有实际意义的組合問題。已經証明,即使对于树形图(Tree)来說,确定它的带宽問題也属于NP—完全类。因此,求出一些特殊类型的图的带宽就更加引人注目。事实上,能够定出其带宽的图很少。除了一些很簡单的情形外,迄今已知的主要結果只有完全偶图K_(m:n)、n維方体Q_n、平面格子图P_m×P_n和柱面上的格子图C_m×P_n。Dewdney在1976年所作的关于图的带宽的一篇綜述报告中,提出了三个沒有解决的問题。其中一个是求环面上格子图C_m×C_n的带宽。本文解决了这个問題,我們得到下述結果: 定理1.当m≠n且min(m,n)≥3时,环面上格子图C_m×C_n的带宽为2min(m,n); 定理2.当n≥3时,环面上格子图C_n×C_n的带宽为2n—1.     

Erds猜测的平面情形

本文用对于阶数的归纳法和对于最小度的穷举法证明了下列定理: 定理.设G是n阶的二边连通的简单平面图,那么G必可表为不超过n—2个回之併。这是Erdos等人在16年前提出的一个猜测的平面情形。