Mixed Connectivity of Cartesian Graph Products and Bundles

Abstract

Mixed connectivity is a generalization of vertex and edge connectivity. A graph is \((p,0)\)-connected, \(p \geq 0\), if the graph remains connected after removal of any \(p – 1\) vertices. A graph is \((p,q)\)-connected, \(p \geq 0\), \(q \geq 0\), if it remains connected after removal of any \(p\) vertices and any \(q – 1\) edges. Cartesian graph bundles are graphs that generalize both covering graphs and Cartesian graph products. It is shown that if graph \(F\) is \((p_F, q_F)\)-connected and graph \(B\) is \((p_B, q_B)\)-connected, then Cartesian graph bundle \(G\) with fibre \(F\) over the base graph \(B\) is \((p_F + p_B, q_F + q_B)\)-connected. Furthermore, if \(q_F + p_B \geq 0\), then \(G\) is also \((p_F + p_B + 1, q_F + p_B – 1)\)-connected. Finally, let graphs \(G_i\), \(i = 1, \ldots, n\), be \((p_i, q_i)\)-connected and let \(k\) be the number of graphs with \(q_i > 0\). The Cartesian graph product \(G = G_1 \Box G_2 \Box \ldots \Box G_n\) is \((\sum p_i, \sum q_i)\)-connected, and, for \(k \geq 1\), it is also \((\sum p_i + k – 1, \sum q_i – k + 1)\)-connected.