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.