SAMS Subject Classification Number: 06

The distance between two vertices $u$ and $v$ in a connected graph $G$ is the length of a shortest $u-v$ path in $G$. The diameter of $G$ is the largest of the distances between all pairs of vertices of $G$. If the removal of not more than $k$ vertices (edges) never disconnects the graph $G$, we say that $G$ is $(k+1)$-connected ($(k+1)$-edge-connected). The $k$-fault diameter and $k$-edge-fault diameter of a $(k+1)$-connected or $(k+1)$-edge connected graph $G$ is the largest diameter of the subgraphs obtained from $G$ by removing up to $k$ vertices and edges respectively.

Few bounds on the fault-(edge)-diameter are known. Recently, the second author [Bounds on the fault-diameter of graphs, Networks 70(2) (2017), 132-140] observed that the $k$-fault diameter of a $(k+1)$-connected graph $G$ with $n$ vertices is bounded from above by $n-k+1$ and showed that this bound can be improved to approximately $\frac{4n}{k+2}$ if $G$ is triangle-free and $\frac{5n}{(k-1{)}^2}$ if $G$ does not contain $4$-cycles. He also gave similar bounds on the $k$-edge-fault-diameter.

In this talk, we present these results and show that the above bound for $C_4$-free graphs can be improved to $\frac{3n}{k^2-k+1}+3k^2-3k+5$ if, in addition, the graph is also bipartite. We also discuss results on the $k$-edge-fault diameter for $(k+1)$-edge connected $C_4$-free and bipartite $C_4$-free graphs. We construct graphs to show that our bounds on the $k$-fault-(edge)-diameter of bipartite $C_4$-free graphs are best possible.