摘要
子集S V(G)称为限制割,若任何点v∈V(G)的邻点集NG(v)都不是S的子集且G-S不连通.若G中存在限制割,则定义限制连通度1κ(G)=min{S:S是G的一个限制割}.考虑了笛卡尔乘积图,证明了:设G=G1×G2×…×Gn,若Gi是满足某些给定条件的ki连通ki正则且围长至少为5的图。
A subset S（∩）V（G） is called a restricted cut, if it does not contain a neighbor-set of any vertex as its subset andG-S is disconnected. If there exists a restricted cut SinG, the restricted connectivity k1 （G） = min{｜S｜ ：S is a restricted cut of G}. The Cartesian product graphs are considered and k1 （G） = 2 n∑i=1 ki- 2 is obtained if for each i = 1,2,… ,n（n ≥ 3）,Gi is a ki-regular ki-connected graph of girth at least 5 and satisfies some given conditions, where G = G1×G2×…×Gn.
基金
Supported by NNSF of China(10271114).
关键词
连通度
限制连通度
正则图
笛卡尔乘积
超立方体
connectivity
restricted connectivity
regular
Cartesian product
hypercube
