三度连通循环图的控制数

p个点0,1,2,…,p—1的循环图Cp【a1,a2,…,ak】是指如下的简单图:顶点i分别与（取模p的同余数r,）邻接,其中a1,a2…ak,为正整数,且循环图Cp【a1,a2…,ak】连通的充要条件是最大公约数(p,三度循环图一定是,其中p为大于2的偶数,。 对于图G及点集,用N[D]表示D的闭邻域。若则称D覆盖v;若N[D]=V（G）,则称D为G的一个控制集,具有最少点数的控制集的基数称为G的控制数,记为（G）。用[x]表示不小于x的最小整数。虽然关于图G的控制数（G）的研究近年来已有了许多结果,但所有的工作几乎都是给出（G）的上、下界或者给出 （G）与其它参数的关系,具体给出某类图的控制数仍然相当困难,所得结果极少。本文构造性地给出了三度连通循环图的控制数。

循环图带宽的上界

给出了连通循环图Ｇ＝Ｃｎ〈ｊ１，ｊ２，…，ｊｒ〉带宽Ｂ（Ｇ）的上界，即Ｂ（Ｇ）≤２ｊｒ，并研究得到了四度连通循环图Ｇ１＝Ｃｍ１ｍ２〈ｋ１ｍ１，ｋ２ｍ２〉的带宽Ｂ（Ｇ１）＝２ｍｉｎ（ｍ１，ｍ２）（ｍ１＝ｇｃｄ（ｍ１ｍ２，ｊ１），ｍ２＝ｇｃｄ（ｍ１ｍ２，ｊ２）），及五度连通循环图Ｇ２＝Ｃｍ１ｍ２〈ｊ１，ｊ２，ｍ１ｍ２／２〉的带宽Ｂ（Ｇ２）＝４ｍｉｎ（ｍ１，ｍ２）（２ｍ１＝ｇｃｄ（ｍ１ｍ２，ｊ１），２ｍ２＝ｇｃｄ（ｍ１ｍ２，ｊ２））．

具有最佳连通性的网络的构造

本文利用连通循环图及其连通度的有关性质,得到了构造具有最佳连通性的循环网络的定理。根据这些定理,可构造出包含著名学者Harary得出的H_(m,n)连通网络在内的最佳连通性网络。