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

Pan, Xiang-feng; Xu, Jun-ming; Lv, Min

J. Univ. Sci. Technol. China 36, No. 3, 237-240 (2006).

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\).

MSC:

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

Keywords:

connectivity; restricted connectivity; regular; Cartesian product; hypercube