A proof of Jean de Rumeur's conjecture

✍ Scribed by Stéphane Perennes

• Book ID: 104294779
• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 276 KB
• Volume: 74
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(97)00003-6

✦ Synopsis

We give an elementary proof of Jean de Rumeur's conjecture stating that in any digraph G of diameter D, such that the sum of the indegree and outdegree of every vertex is at most 2d, the number of vertices is at most 1 +d+d'+ ..' +dD.

Our result implies that known good solutions in the case d + = d = d are also quasi-optimal under the assumption that d + + d -= 2d.