Premium
On super connectivity of Cartesian product graphs
Author(s) -
Lü Min,
Wu Chao,
Chen GuoLiang,
Lv Cheng
Publication year - 2008
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20224
Subject(s) - cartesian product , combinatorics , social connectedness , connectivity , mathematics , graph , product (mathematics) , graph product , discrete mathematics , cartesian coordinate system , vertex connectivity , computer science , pathwidth , line graph , vertex (graph theory) , geometry , psychology , psychotherapist
The super connectivity κ 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 κ. This article provides bounds for the super connectivity κ 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 κ 1 ( K m × K n ) = min{ m + 2 n − 4, 2 m + n − 4} for m + n ≥ 6 and state sufficient conditions to guarantee κ 1 ( K 2 × G ) = 2κ( G ). As a consequence, we immediately obtain the super connectivity of the n ‐cube for n ≥ 3. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008