Mixed connectivity of Cartesian graph products and bundles

Rija Erves; Janez Zerovnik

paper

Mixed connectivity of Cartesian graph products and bundles

arXiv:1002.2508

Abstract

Mixed connectivity is a generalization of vertex and edge connectivity. A graph is $(p, 0)$ -connected, $p > 0$ , if the graph remains connected after removal of any $p - 1$ vertices. A graph is $(p, q)$ -connected, $p \geq 0$ , $q > 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}, q_{B} > 0$ , then $G$ is also $(p_{F} + p_{B} + 1, q_{F} + q_{B} - 1)$ -connected. Finally, let graphs $G_{i}, i = 1, ..., 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} □ G_{2} □ ... □ 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.

Cited by in corpus (1)

Improved upper bounds for vertex and edge fault diameters of Cartesian graph bundles