循环图的连通性及其Hamilton圈

本文的主要结果是在研究循环图结构的基础上,探讨了循环图连通的充要条件,进而证明了连通的循环图都是Hamilton图的一般结论。凡文中没有定义的概念及未加证明的结论,均可在文章1]中见到。定义1 如果(n,i-1)=1,2≤7≤(n+1)/2],则公式 k(i—1)+i(mod n),k∈数集Z,称为标号公式.如果(n,i-1)=m>1,那么矩阵 R={1 1+i-1 … 1+k(i-1)… 2 2+i-1 … 2+k(i-1)……………………………… m m+i-1 … m+k(i-1)…}m×n/m (mod n)可以给2—度循环图G标号,使其邻接矩阵为循环矩阵。R称为图G的标号矩阵,其中k按mod n/m来计算。