Maximum Directed Cuts in Digraphs with Degree Restriction

被引：9

作者：

Lehel, Jenoe ^{[1
,2
]}

Maffray, Frederic ^{[3
]}

Preissmann, Myriam ^{[3
]}

机构：

[1] Univ Memphis, Dept Math Sci, Memphis, TN 38152 USA

[2] Hungarian Acad Sci, Comp & Automat Res Inst, Budapest, Hungary

[3] Lab G Scop, CNRS, F-38031 Grenoble 1, France

来源：

JOURNAL OF GRAPH THEORY | 2009年 / 61卷 / 02期

关键词：

directed cut; maximum cut; directed cut and acyclic graphs; extremal problems; GRAPHS;

D O I：

10.1002/jgt.20374

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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. (C) 2009 Wiley Periodicals, Inc. J Graph Theory 61: 140-156, 2009

引用

页码：140 / 156

页数：17

共 12 条

[1] Maximum directed cuts in acyclic digraphs
Alon, Noga
Bollobas, Bela
Gyarfas, Andras
Lehel, Jeno
Scott, Alex
[J]. JOURNAL OF GRAPH THEORY, 2007, 55 (01) : 1 - 13
[2] AMINI O, 2006, JOURN GRAPH ALG ORL
[3] Berman P., 1999, Automata, Languages and Programming. 26th International Colloquium, ICALP'99. Proceedings (Lecture Notes in Computer Science Vol.1644), P200
[4] LARGEST BIPARTITE SUBGRAPHS IN TRIANGLE-FREE GRAPHS WITH MAXIMUM DEGREE 3
BONDY, JA
LOCKE, SC
[J]. JOURNAL OF GRAPH THEORY, 1986, 10 (04) : 477 - 504
[5] BRANDT R, 2005, J INTERCONNECTION NE, V6, P383
[6] CROPPER M, 2000, CAHIERS LAB LEIBNIZ, V17
[7] Diestel R., 1997, GRADUATE TEXTS MATH, V173
[8] On incidence coloring and star arboricity of graphs
Guiduli, B
[J]. DISCRETE MATHEMATICS, 1997, 163 (1-3) : 275 - 278
[9] MAX CUT in cubic graphs
Halperin, E
Livnat, D
Zwick, U
[J]. JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2004, 53 (02): : 169 - 185
[10] TRIANGLE-FREE PARTIAL GRAPHS AND EDGE COVERING-THEOREMS
LEHEL, J
TUZA, Z
[J]. DISCRETE MATHEMATICS, 1982, 39 (01) : 59 - 65

← 1 2 →