Antisymmetric flows and edge-connectivity

被引：3

作者：

DeVos, M ^{[1
]}

Nesetril, J

Raspaud, A

机构：

[1] Princeton Univ, Dept Appl Math, Princeton, NJ 08544 USA

[2] Univ Bordeaux 1, LaBRI, F-33405 Talence, France

[3] Charles Univ, Inst Theoret Comp Sci, ITI, KAM,Dept Appl Math, Prague 11800, Czech Republic

来源：

DISCRETE MATHEMATICS | 2004年 / 276卷 / 1-3期

关键词：

graph theory;

D O I：

10.1016/S0012-365X(03)00301-7

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let G = (V, E) be a directed graph, let M be an abelian group, and let f : E --> M be a flow. We say that f is antisymmetric if f (E) boolean AND - f (E) = circle divide. Using a theorem of DeVos, Johnson, and Seymour, we improve upon a result of theirs by showing that every directed graph (without the obvious obstruction) has an antisymmetric flow in the group Z(3)(3) x Z(6)(6). We also provide some additional theorems proving the existence of an antisymmetric flow in a smaller group, under the added assumption that G has a certain edge-connectivity. (C) 2003 Elsevier B.V. All rights reserved.

引用

页码：161 / 167

页数：7