TOUGHNESS AND TRIANGLE-FREE GRAPHS

被引：12

作者：

BAUER, D

VANDENHEUVEL, J

SCHMEICHEL, E

机构：

[1] UNIV TWENTE,FAC APPL MATH,7500 AE ENSCHEDE,NETHERLANDS

[2] SAN JOSE STATE UNIV,DEPT MATH & COMP SCI,SAN JOSE,CA 95192

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 1995年 / 65卷 / 02期

关键词：

D O I：

10.1006/jctb.1995.1051

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In this paper, we prove that there exist triangle-free graphs with arbitrarily large toughness, thereby settling a longstanding open question. We also explore the problem of whether there exists a t-tough, n/(t + 1)-regular, triangle-free graph on n vertices for various values of t, and provide a relatively complete answer for small values of t. (C) 1995 Academic Press, Inc.

引用

页码：208 / 221

页数：14

共 17 条

[1]

ALON N, 1993, TOUGH RANSEY GRAPHS

[2] PANCYCLISM IN HAMILTONIAN GRAPHS [J].

AMAR, D ;

FLANDRIN, E ;

FOURNIER, I ;

GERMA, A .

DISCRETE MATHEMATICS, 1991, 89 (02) :111-131

[3] LONG CYCLES IN GRAPHS WITH PRESCRIBED TOUGHNESS AND MINIMUM DEGREE [J].

BAUER, D ;

BROERSMA, HJ ;

VANDENHEUVEL, J ;

VELDMAN, HJ .

DISCRETE MATHEMATICS, 1995, 141 (1-3) :1-10

[4]

BAUER D, 1995, 9501 STEV I TECHN TE

[5]

BONDY JA, 1976, GRAPH THEORY APPLICA

[6]

BRANDT S, COMMUNICATION

[7]

Chvatal V., 1973, Discrete Mathematics, V5, P215, DOI 10.1016/0012-365X(73)90138-6

[8]

CHVATAL V, 1973, NEW DIRECTIONS THEOR, P65

[9]

Chvatal V., 1972, DISCRETE MATH, V2, P111, DOI [DOI 10.1016/0012-365X(72)90079-9, 10.1016/0012-365X(72)90079-9]

[10]

Descartes B., 1947, EUREKA, V9, P21

← 1 2 →