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\ge 0$, if the graph remains connected after removal of any $p–1$ vertices. A graph is $(p,q)$-connected, $p\ge 0$, $q\ge 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\ge 0$, then $G$ is also $(p_F+p_B+1,q_F+p_B–1)$-connected. Finally, let graphs $G_i$, $i=1,\dots ,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\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{G}_2\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}\dots \mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{G}_n$ is $(\sum p_i,\sum q_i)$-connected, and, for $k\ge 1$, it is also $(\sum p_i+k–1,\sum q_i–k+1)$-connected.