Contractible edges in 7-connected graphs

被引:1
作者
Ji, SJ [1 ]
Xudong, Y [1 ]
机构
[1] Guangxi Normal Univ, Dept Math, Guilin 541004, Peoples R China
关键词
D O I
10.1007/s00373-005-0621-4
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
An edge of a k-connected graph is said to be a k-contractible edge, if its contraction yields again a k-connected graph. A noncomplete k-connected graph possessing no k-contractible edges is called contraction critical k-connected. Recently, Kriesell proved that every contraction critical 7-connected graph has two distinct vertices of degree 7. And he guessed that there are two vertices of degree 7 at distance one or two. In this paper, we give a proof to his conjecture.
引用
收藏
页码:445 / 457
页数:13
相关论文
共 11 条
[1]  
DIESTEL R, 1997, GRADUAATE TEXTS MATH, V173
[2]   CONTRACTILE EDGES IN N-CONNECTED GRAPHS WITH MINIMUM DEGREE GREATER THAN OR EQUAL TO [5N/4] [J].
EGAWA, Y .
GRAPHS AND COMBINATORICS, 1991, 7 (01) :15-21
[3]  
JIANJI S, UNPUB NEW DEGREE SUM
[4]   A degree sum condition for the existence of a contractible edge in a k-connected graph [J].
Kriesell, M .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2001, 82 (01) :81-101
[5]   PROPERTY OF ATOMS OF FINITE GRAPHS [J].
MADER, W .
ARCHIV DER MATHEMATIK, 1971, 22 (03) :333-&
[6]   GENERALIZATIONS OF CRITICAL CONNECTIVITY OF GRAPHS [J].
MADER, W .
DISCRETE MATHEMATICS, 1988, 72 (1-3) :267-283
[7]   UNCONTRACTABLE 4-CONNECTED GRAPHS [J].
MARTINOV, N .
JOURNAL OF GRAPH THEORY, 1982, 6 (03) :343-344
[8]   NONSEPARATING CYCLES IN K-CONNECTED GRAPHS [J].
THOMASSEN, C .
JOURNAL OF GRAPH THEORY, 1981, 5 (04) :351-354
[9]  
Tutte W., 1961, INDAG MATH, V64, P441
[10]  
XUDONG Y, 2004, ADV MATH, V33, P441