The Removable Edges and the Contractible Subgraphs of 5-Connected Graphs

被引：3

作者：

Qin, Chengfu ^{[1
]}

Guo, Xiaofeng ^{[2
]}

Ando, Kiyoshi ^{[3
]}

机构：

[1] Guangxi Teachers Educ Univ, Sch Math Sci, Nanning 530001, Peoples R China

[2] Xiamen Univ, Dept Math, Xiamen 310065, Fujian, Peoples R China

[3] Univ Electrocommun, Dept Informat & Commun Engn, Chofugao Ku, Chofu, Tokyo 1828585, Japan

来源：

GRAPHS AND COMBINATORICS | 2015年 / 31卷 / 01期

基金：

中国国家自然科学基金;

关键词：

5-connected graph; Contractible subgraph; Removable edge; Minor minimal; CONNECTIVITY; VERTICES; NUMBER;

D O I：

10.1007/s00373-013-1368-y

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

An edge of a k-connected graph G is said to be k-removable if G - e is still k-connected. A subgraph H of a k-connected graph is said to be k-contractible if its contraction, that is, identification every component of H to a single vertex, results again a k-connected graph. In this paper, we show that there is either a removable edge or a contractible subgraph in a 5-connected graph which contains an edge with both endvertices have degree more than five. Thus every edge of minor minimal 5-connected graph is incident to at least one vertex of degree 5.

引用

页码：243 / 254

页数：12

共 18 条

[1] Vertices of degree 5 in a contraction critically 5-connected graph
Ando, K
Kaneko, A
Kawarabayashi, K
[J]. GRAPHS AND COMBINATORICS, 2005, 21 (01) : 27 - 37
[2] The number of vertices of degree 5 in a contraction-critically 5-connected graph
Ando, Kiyoshi
Iwase, Takashi
[J]. DISCRETE MATHEMATICS, 2011, 311 (17) : 1925 - 1939
[3] Some structural properties of minimally contraction-critically 5-connected graphs
Ando, Kiyoshi
Qin Chengfu
[J]. DISCRETE MATHEMATICS, 2011, 311 (13) : 1084 - 1097
[4] A Local Structure Theorem on 5-Connected Graphs
Ando, Kiyoshi
[J]. JOURNAL OF GRAPH THEORY, 2009, 60 (02) : 99 - 129
[5] Bondy J. A., 1976, Graduate Texts in Mathematics, V290
[6] FIJAVZ G, 2001, THESIS U LJUBLJANA
[7] Average degree and contractibility
Kriesell, M
[J]. JOURNAL OF GRAPH THEORY, 2006, 51 (03) : 205 - 224
[8] A survey on contractible edges in graphs of a prescribed vertex connectivity
Kriesell, M
[J]. GRAPHS AND COMBINATORICS, 2002, 18 (01) : 1 - 30
[9] How to contract an essentially 6-connected graph to a 5-connected graph
Kriesell, Matthias
[J]. DISCRETE MATHEMATICS, 2007, 307 (3-5) : 494 - 510
[10] Contractions, cycle double covers, and cyclic colorings in locally connected graphs
Kriesell, Matthias
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2006, 96 (06) : 881 - 900

← 1 2 →