On bipartitions of directed graphs with small semidegree
Abstract
Let D be a directed graph. The minimum semidegree of D is defined to be the minimum value of the minimum outdegree and the minimum indegree of D. For nonempty sets S,T⊆V(D), we use e(S,T) to denote the number of arcs in D from S to T. If D has m arcs and positive minimum semidegree, then we show that D admits a bipartition V(D)=V1∪V2 such that min{e(V1,V2),e(V2,V1)}≥(1∕6+o(1))m. We also prove that if the minimum semidegree is at least two (or...
Paper Details
Title
On bipartitions of directed graphs with small semidegree
Published Date
Feb 1, 2020
Volume
84
Pages
103039 - 103039
Citation AnalysisPro
You’ll need to upgrade your plan to Pro
Looking to understand the true influence of a researcher’s work across journals & affiliations?
- Scinapse’s Top 10 Citation Journals & Affiliations graph reveals the quality and authenticity of citations received by a paper.
- Discover whether citations have been inflated due to self-citations, or if citations include institutional bias.
Notes
History