On the distance connectivity of graphs and digraphs (Q1322268): Difference between revisions

In a finite connected directed graph \(G=(V,E)\) of diameter \(D\), define the parameter \(l=l(G)\) to be the greatest integer \(\leq D\) such that for all \(x,y \in V\), with directed distance \(d(x,y) \leq l\), there exists a unique \(x \to y\) path of length \(d(x,y)\), while if \(d(x,y)<l\), then there is none of length \(d(x,y)+1\). For \(1 \leq t \leq D\), define \(\kappa (t)=\min \{| S |:S\) separates \(y\) from \(x\); \(x,y \in V\); \(d(x,y) \geq t\}\). Let \(\kappa\) and \(\lambda\) denote the usual vertex- and edge- connectivity of \(G\). It is shown that if \(G\) has minimum valence \(r>1\), then: (a) if \(\kappa<r\), then \(D \geq 2l\) and \(\kappa = \kappa (2l)\); (b) if \(\lambda<r\), then \(D \geq 2l+1\) and \(\lambda = \lambda (2l+1)\). Results for (undirected) graphs are obtained as corollaries. In the special case of bipartite directed graphs, the second condition in the definition of \(l\) being vacuous, slightly sharper inequalities may be obtained.