一类笛卡尔乘积图的等周数

Isoperimetric number of a kind of Cartesian product graph

等周数是互联网络的一个重要参数,它与图的连通性和二部带宽等参数密切相关.A z izog lu和Egec iog lu运用嵌入的方法得到了形如Pk×Pk×…×Pk的笛卡尔乘积图的等周数.通过将S嵌入以V(S)为顶点的完全有向图Kd(d=V(S))的方法给出i(S)的下界,将上述嵌入方法推广,从而得到了形如Pl1×Pl2×…×Pla×Cm1×Cm2×…×Cmb×Kn1×Kn2×…×Knc的笛卡尔乘积图的等周数.讨论了笛卡尔乘积图的等周数与二部带宽和Cheeger常数之间的关系,并给出了循环图Ck的d重直积图的等周数.

Isoperimetric number is one of the crucial parameters of interconnection networks closely related to the connectivity and parameters, such as bisection width of graphs. Azizoglu and Egecioglu obtained the isoperimetric number of Cartesian product graphs in the form of Pk × Pk ×…… × Pk by an embedding technique. In order to generalize such a technique, the isoperimetric number of Cartesian product graphs with form of Pl1 × Pl2 ×…… × Pla × Cm1 × Cm2 × …… × Cmb × Kn1 × Kn2 × …… × Knc is achieved by embedding a graph S into a completed directed graph Kd（d =｜V（S） ｜ whose vertices are V（S）. In the end, the relationship between the isoperimetric number of Cartesian product graphs and bisection width of graphs and Cheeger constant is discussed, and the isoperimetric number of d-dimensional k-torus Tk^d is given.