On restricted connectivity of some Cartesian product graphs. (English) Zbl 1259.05101

Summary: A subset \(S \subset V(G)\) is called a restricted cut, if it does not contain a neighbor-set of any vertex as its subset and \(G - S\) is disconnected. If there exists a restricted cut \(S\) in \(G\), the restricted connectivity \(\kappa^1(G) = \min\{|S| :S\) is a restricted cut of \(G\}\). The Cartesian product graphs are considered and \(\kappa^1(G) = 2\sum^2_{i=1} k_i - 2\) is obtained if for each \(i =1,2,\dots,n\) (\(n \geq 3\)), \(G_i\) is a \(k_i\)-regular \(k_i\) connected graph of girth at least 5 and satisfies some given conditions, where \(G = G_1 \times G_2 \times \dots \times G_n\).


05C40 Connectivity
05C76 Graph operations (line graphs, products, etc.)
05C65 Hypergraphs