The edge fault-diameter of Cartesian graph bundles (Q1024302): Difference between revisions

The Cartesian product of two graphs \(G_1\) and \(G_2\), \(G_1\square G_2\), has vertex set set \(V(G_1)\times V(G_2)\). Two vertices \((u_1, v_1)\) and \((u_2, v_2)\) are adjacent in \(G_1\square G_2\) if either \(u_1u_2\in E(G_1)\) and \(v_1=v_2\) or \(v_1v_2\in E(G_2)\) and \(u_1=u_2\). A graph \(G\) is a Cartesian graph bundle with fibre graph \(F\) over the base graph \(B\) if there is a mapping \(p: G \rightarrow B\) such that for each vertex \(v\in V(B)\), \(p^{-1}(v)\) is isoporphic to \(F\) and for each edge \(e\in E(B)\), \(p^{-1}(e)\) is isomorphic to \(F\square K_2\), where \(K_2\) is the graph with two vertices and one edge. For \(k_F\)-edge connected graph \(F\) and \(k_B\)-edge connected graph \(B\) and the graph bundle \(G\) with fibre \(F\) over base graph \(B\), the authors prove that (1) the edge-connectivity of \(G\) is at least \(k_F+k_B\) and (2) \(\mathcal{D}_{a+b+1}(G)\leq \mathcal{D}_a(F)+\mathcal{D}_b(B)+1\) for \(a<k_F, b< k_B\). (For a \(k\)-edge connected graph \(H\) and \(0\leq c<k\), \(\mathcal{D}_c(H)\) is the largest diameter among subgraphs of \(H\) with \(c\) edges deleted.)