Maximum directed cuts in acyclic digraphs

Noga Alon; Béla Bollobás; András Gyárfás; Jenö Lehel; Alex Scott

doi:10.1002/jgt.20215

Maximum directed cuts in acyclic digraphs

Noga Alon, Béla Bollobás, András Gyárfás, Jenö Lehel, Alex Scott

Research output: Contribution to journal › Article › peer-review

26 Scopus citations

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.

Original language	English (US)
Pages (from-to)	1-13
Number of pages	13
Journal	Journal of Graph Theory
Volume	55
Issue number	1
DOIs	https://doi.org/10.1002/jgt.20215
State	Published - May 2007
Externally published	Yes

All Science Journal Classification (ASJC) codes

Geometry and Topology

Keywords

Directed and acyclic graphs
Directed cut
Extremal problems
Maximum cut

Access to Document

10.1002/jgt.20215

Cite this

@article{ad307784509443ca940f08ce5e0a7ff0,

title = "Maximum directed cuts in acyclic digraphs",

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.",

keywords = "Directed and acyclic graphs, Directed cut, Extremal problems, Maximum cut",

author = "Noga Alon and B{\'e}la Bollob{\'a}s and Andr{\'a}s Gy{\'a}rf{\'a}s and Jen{\"o} Lehel and Alex Scott",

year = "2007",

month = may,

doi = "10.1002/jgt.20215",

language = "English (US)",

volume = "55",

pages = "1--13",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "1",

}

TY - JOUR

T1 - Maximum directed cuts in acyclic digraphs

AU - Alon, Noga

AU - Bollobás, Béla

AU - Gyárfás, András

AU - Lehel, Jenö

AU - Scott, Alex

PY - 2007/5

Y1 - 2007/5

N2 - 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.

AB - 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.

KW - Directed and acyclic graphs

KW - Directed cut

KW - Extremal problems

KW - Maximum cut

UR - http://www.scopus.com/inward/record.url?scp=34248153673&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34248153673&partnerID=8YFLogxK

U2 - 10.1002/jgt.20215

DO - 10.1002/jgt.20215

M3 - Article

AN - SCOPUS:34248153673

SN - 0364-9024

VL - 55

SP - 1

EP - 13

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 1

ER -

Maximum directed cuts in acyclic digraphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this