𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Maximum directed cuts in acyclic digraphs

✍ Scribed by Noga Alon; Béla Bollobás; András Gyárfás; Jenő Lehel; Alex Scott

Publisher
John Wiley and Sons
Year
2007
Tongue
English
Weight
152 KB
Volume
55
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

It is easily shown that every digraph with m edges has a directed cut of size at least m/4, and that 1/4 cannot be replaced by any larger constant. We investigate the size of the largest directed cut in acyclic digraphs, and prove a number of related results concerning cuts in digraphs and acyclic digraphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 1–13, 2007

📜 SIMILAR VOLUMES

Maximum directed cuts in digraphs with d
Maximum directed cuts in digraphs with degree restriction
✍ Jenö Lehel; Frédéric Maffray; Myriam Preissmann 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 173 KB

## Abstract For integers __m, k__≥1, we investigate the maximum size of a directed cut in directed graphs in which there are __m__ edges and each vertex has either indegree at most __k__ or outdegree at most __k__. © 2009 Wiley Periodicals, Inc. J Graph Theory

Directed Triangles in Digraphs
Directed Triangles in Digraphs
✍ Jian Shen 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 144 KB

Let c be the smallest possible value such that every digraph on n vertices with minimum outdegree at least cn contains a directed triangle. It was conjectured by Caccetta and Ha ggkvist in 1978 that c=1Â3. Recently Bondy showed that c (2 -6&3)Â5=0.3797... by using some counting arguments. In this no

A Matrix for Counting Paths in Acyclic D
A Matrix for Counting Paths in Acyclic Digraphs
✍ Richard P. Stanley 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 178 KB

We define a matrix A associated with an acyclic digraph 1, such that the coefficient of z j in det(I+zA) is the number of j-vertex paths in 1. This result is actually a special case of a more general weighted version.

Maximum acyclic and fragmented sets in r
Maximum acyclic and fragmented sets in regular graphs
✍ Penny Haxell; Oleg Pikhurko; Andrew Thomason 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB

## Abstract We show that a typical __d__‐regular graph __G__ of order __n__ does not contain an induced forest with around ${2 {\rm In} d \over d}$ vertices, when __n__ ≫ __d__ ≫ 1, this bound being best possible because of a result of Frieze and Łuczak [6]. We then deduce an affirmative answer to