Vertices of Degree 5 in a Contraction Critically 5-connected Graph

被引：1

作者：

Kiyoshi Ando

Atsushi Kaneko

Ken-ichi Kawarabayashi

机构：

[1] The University of Electro-Communications,Department of Information and Communication Engineering

[2] Kogakuin University,Department of Computer Science and Communication Engineering

[3] Tohoku University,Graduate School of Information Sciences

来源：

Graphs and Combinatorics | 2005年 / 21卷

关键词：

5-Connected graph; Contractible edge; Contraction critically ; -connected; 05C40;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

An edge of a k-connected graph is said to be k-contractible if the contraction of the edge results in a k-connected graph. A k-connected graph with no k-contractible edge is said to be contraction critically k-connected. We prove that a contraction critically 5-connected graph on n vertices has at least n/5 vertices of degree 5. We also show that, for a graph G and an integer k greater than 4, there exists a contraction critically k-connected graph which has G as its induced subgraph.

引用

页码：27 / 37

页数：10

共 17 条

[1] Vertices of degree 5 in a contraction critically 5-connected graph
Ando, K
Kaneko, A
Kawarabayashi, K
GRAPHS AND COMBINATORICS, 2005, 21 (01) : 27 - 37
[2] Trivially noncontractible edges in a contraction critically 5-connected graph
Ando, K
DISCRETE MATHEMATICS, 2005, 293 (1-3) : 61 - 72
[3] Vertices of degree 6 in a contraction critically 6-connected graph
Ando, K
Kaneko, A
Kawarabayashi, K
DISCRETE MATHEMATICS, 2003, 273 (1-3) : 55 - 69
[4] Removable edges in a 5-connected graph and a construction method of 5-connected graphs
Xu, Liqiong
Guo, Xiaofeng
DISCRETE MATHEMATICS, 2008, 308 (09) : 1726 - 1731
[5] The number of vertices of degree 7 in a contraction-critical 7-connected graph
Min, Li
Yuan Xudong
Su Jianji
DISCRETE MATHEMATICS, 2008, 308 (24) : 6262 - 6268
[6] The contractible subgraph of 5-connected graphs
Chengfu Qin
Xiaofeng Guo
Weihua Yang
Czechoslovak Mathematical Journal, 2013, 63 : 671 - 677
[7] A Local Structure Theorem on 5-Connected Graphs
Ando, Kiyoshi
JOURNAL OF GRAPH THEORY, 2009, 60 (02) : 99 - 129
[8] Vertices of Degree 9 in Contraction Critical 8-Connected Graphs
Yang, Yingqiu
ARS COMBINATORIA, 2017, 131 : 107 - 122
[9] Contractible Edges in a 4-Connected Graph with Vertices of Degree Greater Than Four
Kiyoshi Ando
Yoshimi Egawa
Graphs and Combinatorics, 2007, 23 : 99 - 115
[10] Contractible edges in a 4-connected graph with vertices of degree greater than four
Ando, Kiyoshi
Egawa, Yoshimi
GRAPHS AND COMBINATORICS, 2007, 23 (Suppl 1) : 99 - 115

← 1 2 →