一些笛卡尔乘积图的限制连通度(英文)  

On restricted connectivity of some Cartesian product graphs

作　　者：潘向峰[1] 徐俊明[1] 吕敏[1] 

机构地区：[1]中国科学技术大学数学系,安徽合肥230026

出　　处：《中国科学技术大学学报》2006年第3期237-240,共4页JUSTC

基　　金：Supported by NNSF of China(10271114).

摘　　要：子集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.

关 键 词：连通度 限制连通度 正则图 笛卡尔乘积 超立方体 

分 类 号：O157.5[理学—数学]