Vertices of degree \(k\) in a minimally \(k\)-edge-connected digraph
Let \(D=(V,E)\) be a simple finite digraph without loops which is minimally \(k\)-edge-connected, i.e. the removal of any edge destroys the \(k\)-edge-connectivity. If \(\delta^+(x)\) denotes the outdegree for a vertex \(x \in V(D)\) (and \(\delta^-(x)\) the indegree) and \(u^+(D)\) the number of vertices \(x\) in \(D\) such that \(\delta^+(x)=k<\delta^-(x)\) (and \(u^-(D)\) and \(u^{\pm}(D)\), respectively, the number of vertices \(x\) in \(D\) such that \(\delta^+(x)>k=\delta^-(x)\) and \(\delta^+(x)=\delta^-(x)=k\), respectively) then it is proved that \(u^+(D)+2u^{\pm}(D)+u^-(D) \geq 2k+2\) which establishes a conjecture of \textit{W. Mader} [Bolyai Soc. Math. Stud. 2, 423-449 (1996; Zbl 0849.05048)]. Moreover, lower bounds for \(u^+(D)+u^{\pm}(D)+u^-(D)\) are presented.
scientific article; zbMATH DE number 1453339