On super connectivity of Cartesian product graphs

被引：23

作者：

Lue, Min ^{[1
]}

Wu, Chao ^{[1
]}

Chen, Guo-Liang ^{[1
]}

Lv, Cheng ^{[2
]}

机构：

[1] Univ Sci & Technol China, Dept Comp Sci & Technol, Anhui Prov Most Key Co Lab High Performance Comp, Hefei 230026, Anhui, Peoples R China

[2] Anhui Inst Architecture & Ind, Dept Math & Phys, Hefei, Anhui, Peoples R China

来源：

NETWORKS | 2008年 / 52卷 / 02期

基金：

中国国家自然科学基金;

关键词：

super connectivity; cartesian product; maximally connected graphs; super connected graphs;

D O I：

10.1002/net.20224

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

The super connectivity kappa(1) of a connected graph G is the minimum number of vertices whose deletion results in a disconnected graph without isolated vertices; this is a more refined index than the connectivity parameter K. This article provides bounds for the super connectivity kappa(1) of the Cartesian product of two connected graphs, and thus generalizes the main result of Shieh on the super connectedness of the Cartesian product of two regular graphs with maximum connectivity. Particularly, we determine that kappa(1) (K-m x K-n) = min (m + 2n - 4,2m + n - 4] for m + n > 6 and state sufficient conditions to guarantee kappa(1) (K-2 x G) = 2 kappa (G). As a consequence, we immediately obtain the super connectivity of the n-cube for n > 3. (C) 2008 Wiley Periodicals, Inc.

引用

页码：78 / 87

页数：10

共 21 条

[1] On the restricted connectivity and superconnectivity in graphs with given girth [J].