Vertices of degree \(k\) in a minimally \(k\)-edge-connected digraph
type: Item
instance of: scholarly article
title: Vertices of degree \(k\) in a minimally \(k\)-edge-connected digraph
zbMATH Open document ID: 0953.05028
DOI: 10.1016/S0012-365X(99)00362-3
published in: Discrete Mathematics
publication date: 2000-07-24T00:00:00Z
review text: 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.
reviewed by: Arnfried Kemnitz
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1453339
zbMATH Keywords: digraph
zbMATH Keywords: indegree
zbMATH Keywords: outdegree
zbMATH Keywords: \(k\)-edge-connected
zbMATH Keywords: \(k\)-cut
zbMATH Keywords: crossing-free
zbMATH Keywords: terminal
author: Xudong Yuan
author: Mao-Cheng Cai
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1453339