Mixed connectivity of Cartesian graph products and bundles.

zbMATH Open1413.05201arXiv1002.2508MaRDI QIDQ2828892FDOQ2828892

Authors: Rija Erveš, Janez Žerovnik 

Publication date: 26 October 2016

Published in: Ars Combinatoria (Search for Journal in Brave)

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, $pgeq0$, $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,\mathrm{...},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\mathrm{...}Box{G}_n$ is $(sum{p}_i,sum{q}_i)$-connected, and, for $kgeq1$, it is also $(sum{p}_i+k-1,sum{q}_i-k+1)$-connected.

Full work available at URL: https://arxiv.org/abs/1002.2508

Recommendations

• Mixed fault diameter of Cartesian graph bundles. II.
• Mixed fault diameter of Cartesian graph bundles
• The edge fault-diameter of Cartesian graph bundles
• Connectivity of Cartesian product graphs
• Improved upper bounds for vertex and edge fault diameters of Cartesian graph bundles

zbMATH Keywords

fault toleranceinterconnection networkvertex connectivityedge connectivityCartesian graph bundleCartesian graph productmixed connectivity

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Connectivity (05C40) Graph operations (line graphs, products, etc.) (05C76)

Cited In (2)

• On the mixed connectivity conjecture of Beineke and Harary
• The complexity of mixed-connectivity

This page was built for publication: Mixed connectivity of Cartesian graph products and bundles.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2828892)