Degree sum and nowhere-zero 3-flows

被引：26

作者：

Fan, Genghua ^{[1
]}

Zhou, Chuixiang ^{[1
]}

机构：

[1] Fuzhou Univ, Ctr Discrete Math, Fuzhou 350002, Peoples R China

来源：

DISCRETE MATHEMATICS | 2008年 / 308卷 / 24期

关键词：

Degree sum; Nowhere-zero; 3-flow; 3-flow contractible;

D O I：

10.1016/j.disc.2007.11.045

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let G be a simple graph on n vertices. In this paper, we prove that if G satisfies the condition that d(x) + d(y) >= n for each xy is an element of E(G), then G has no nowhere-zehro 3-flow if and only if G is either one of the five graphs on at most 6 vertices or one of a very special class of graphs on at least 6 vertices. (c) 2007 Elseiver B.V. All rights reserved.

引用

页码：6233 / 6240

页数：8

共 10 条

[1]

Bondy J.A., 2008, GRAD TEXTS MATH

[2] Nowhere-zero Z3-flows through Z3-connectivity [J].

DeVos, M ;

Xu, R ;

Yu, GX .

DISCRETE MATHEMATICS, 2006, 306 (01) :26-30

[3]

FAN G, NOWHERE ZERO 3 UNPUB

[4] GROUP CONNECTIVITY OF GRAPHS - A NONHOMOGENEOUS ANALOG OF NOWHERE-ZERO FLOW PROPERTIES [J].

JAEGER, F ;

LINIAL, N ;

PAYAN, C ;

TARSI, M .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1992, 56 (02) :165-182

[5] Group connectivity of graphs with diameter at most 2 [J].

Lai, HJ ;

Yao, XJ .

EUROPEAN JOURNAL OF COMBINATORICS, 2006, 27 (03) :436-443

[6] Nowhere-zero 3-flows in locally connected graphs [J].

Lai, HJ .

JOURNAL OF GRAPH THEORY, 2003, 42 (03) :211-219

[7]

Lai HJ, 2000, GRAPH COMBINATOR, V16, P165, DOI 10.1007/s003730050014

[8] NOWHERE-ZERO 6-FLOWS [J].

SEYMOUR, PD .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1981, 30 (02) :130-135

[9] A CONTRIBUTION TO THE THEORY OF CHROMATIC POLYNOMIALS [J].

TUTTE, WT .

CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES, 1954, 6 (01) :80-91

[10] Nowhere-zero flows in tensor product of graphs [J].

Zhang, Zhao ;

Zheng, Yirong ;

Mamut, Aygul .

JOURNAL OF GRAPH THEORY, 2007, 54 (04) :284-292

← 1 →