Mixed connectivity of Cartesian graph products and bundles

作者：Erves Rija^*; Zerovnik Janez^*

来源：Ars Combinatoria, 2016, 124: 49-64.

• vertex connectivity
• edge connectivity
• mixed connectivity
• Cartesian graph bundle
• Cartesian graph product
• interconnection network
• fault tolerance

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 >= 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)square G(2)square . . . square G(n) is (Sigma p(i), Sigma q(i))-connected, and, for k >= 1, it is also (Sigma p(i) + k - 1, Sigma q(i) - k + 1)-connected.

• 出版日期2016-1