Covering the edges of digraphs in \mathscrD(3,3) and \mathscrD(4,4) with directed cuts

2011/09/21 by Yandong Bai, Binlong Li, Bai, Yandong +3 · 1 citation
Computer Science · Engineering · Mathematics · #05C20 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #graph theory and CDMA systems #math.CO #msc:05C20

paper · pdf · doi:10.48550/arxiv.1109.4671

openalex publication_date 2011/09/21 · arxiv created 2012/02/03 · arxiv updated 2012/02/06 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

For nonnegative integers k and l, let \mathscrD(k,l) denote the family of digraphs in which every vertex has either indegree at most k or outdegree at most l. In this paper we prove that the edges of every digraph in \mathscrD(3,3) and \mathscrD(4,4) can be covered by at most five directed cuts and present an example in \mathscrD(3,3) showing that this result is best possible.

Cited by

• Degrees in oriented hypergraphs and Ramsey p-chromatic number

Related

• Cut covers of acyclic digraphs
• Maximum directed cuts in digraphs with degree restriction
• Subdivisions in digraphs of large out-degree or large dichromatic number
• A note on directed 4-cycles in digraphs
• Subdivisions with congruence constraints in digraphs of large chromatic number