共 17 条
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 条