Disjoint directed cycles

被引：37

作者：

Alon, N ^{[1
]}

机构：

[1] TEL AVIV UNIV,DEPT MATH,RAYMOND & BEVERLY SACKLER FAC EXACT SCI,IL-69978 TEL AVIV,ISRAEL

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 1996年 / 68卷 / 02期

关键词：

D O I：

10.1006/jctb.1996.0062

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

It is shown that there exists a positive epsilon SO that for any integer k, every directed graph with minimum outdegree at least k contains at least epsilon k vertex disjoint cycles. On the other hand, for every ii there is a digraph with minimum outdegree k which does not contain two vertex or edge disjoint cycles of the same length. (C) 1996 Academic Press, Inc.

引用

页码：167 / 178

页数：12

共 12 条

[1] CYCLES OF LENGTH-OMICRON MODULO-KAPPA IN DIRECTED-GRAPHS [J].

ALON, N ;

LINIAL, N .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1989, 47 (01) :114-119

[2]

Alon N, 1996, J GRAPH THEOR, V22, P231, DOI 10.1002/(SICI)1097-0118(199607)22:3<231::AID-JGT3>3.3.CO

[3]

2-O

[4] THE STRONG CHROMATIC NUMBER OF A GRAPH [J].

ALON, N .

RANDOM STRUCTURES & ALGORITHMS, 1992, 3 (01) :1-7

[5]

Alon N., 1992, PROBABILISTIC METHOD

[6]

Berge C, 1976, Graphs and Hypergraphs

[7] CYCLES IN DIGRAPHS - A SURVEY [J].

BERMOND, JC ;

THOMASSEN, C .

JOURNAL OF GRAPH THEORY, 1981, 5 (01) :1-43

[8]

HAGGKVIST R, 1985, CYCLES GRAPHS, V115, P269

[9]

Lovasz L., 1979, COMBINATORIAL PROBLE

[10]

THOMAS L, 1985, DISCOVER, V6, P85

← 1 2 →