
doi: 10.1002/net.20224
AbstractThe 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(Km × Kn) = min{m + 2n − 4, 2m + n − 4} for m + n ≥ 6 and state sufficient conditions to guarantee κ1(K2 × 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
Connectivity, Extremal problems in graph theory, maximally connected graphs, Cartesian product, super connectivity, super connected graphs
Connectivity, Extremal problems in graph theory, maximally connected graphs, Cartesian product, super connectivity, super connected graphs
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 18 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
