Contractible edges in triangle-free graphs
Contractible edges in triangle-free graphs
复制标题
无三角形图中的可收缩边
DOI：
10.1007/bf02579387
复制
发表时间：
1986
期刊：
影响因子：
1.1
通讯作者：
Akira Saito
中科院分区：
文献类型：
--
作者：
Y. Egawa;H. Enomoto;Akira Saito
一个图的边称为k-可收缩的，如果边的收缩导致k-连通图。[5]证明了围长至少为4的k-连通图都有ak-可缩边。本文研究了无三角形图中k-可收缩边的分布，证明了：当k ≥ 2时，围长至少为4且阶n ≥ 3 k的k-连通图不存在+（3/2）k ~ 2 - 3 k或更多k-可收缩边.
An edge of a graph is calledk-contractibleif the contraction of the edge results in ak-connected graph. Thomassen [5] proved that everyk-connected graph of girth at least four has ak-contractible edge. In this paper, we study the distribution ofk-contractible edges in triangle-free graphs and show the following: Whenk≧2, everyk-connected graph of girth at least four and ordern≧3k, hasn+(3/2)k2-3kor morek-contractible edges.