循环图带宽的上界

Upper limit of band width of circulant graphs

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

The upper limit of band width B(G ) of connected circulant graphs G=C n(j 1,j 2,…,j r 〉 is given as B(G)≤2j r . The band width of connected circulant graphs of fourth degree G 1=C m 1m 2 〈k 1m 1,k 2m 2〉 and that of fifth degree G 2=C m 1m 2 〈j 1,j 2,m 1m 2/2 〉,is obtained after investigation to be B(G 1) =2min( m 1,m 2)(m 1=gcd( m 1m 2,j 1), m 2=gcd( m 1m 2,j 2)) and B(G 2)=4min( m 1,m 2)(2m 1=gcd( m 1m 2,j 1),2m 2=gcd( m 1m 2,j 2)),respectively.