19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

Mixed fault diameter of Cartesian graph bundles

Presented by Dr. Janez ŽEROVNIK
Type: Oral presentation
Track: Metric Graph Theory


Mixed fault diameter $D_{(p,q)}(G)$ is the maximum diameter among all subgraphs obtained from graph $G$ by deleting $p$ vertices and $q$ edges. A graph is $(p,q)$+connected if it remains connected after removal of any $p$ vertices and any $q$ edges. Mixed connectivity is a generalization of a vertex and an edge connectivity, and mixed fault diameter generalizes both vertex fault diameter and edge fault diameter. Cartesian graph bundles are graphs that generalize Cartesian graph products. Let $F$ be $(p,q)$+connected graph and $B \not= K_2$ be a connected graph. Upper bounds for the mixed fault diameter of Cartesian graph bundle $G$ with fibre $F$ are given. We prove that if $q>0$, then $D_{(p+1,q)} (G)\leq D_{(p,q)}(F)+ D(B)$, and if $q=0$ and $p>0$, then $D_{(p+1,0)} (G)\leq \max \{ D_{(p,0)} (F), D_{(p-1,1)}(F)\}+ D(B)$. In case when $p=q=0$ the fault diameter is determined exactly.


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors