Covering contractible edges in 2-connected graphs

被引:0
作者
Chan, Tsz Lung [1 ]
机构
[1] Univ Hamburg, Math Seminar, Bundesstr 55, D-20146 Hamburg, Germany
来源
AUSTRALASIAN JOURNAL OF COMBINATORICS | 2018年 / 70卷
关键词
D O I
暂无
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
In this paper we prove that, for any 2-connected graph G nonisomorphic to K-3, the set of contractible edges EC(G) cannot be covered by one vertex. All 2-connected graphs whose contractible edges can be covered by exactly two vertices are characterized. We also prove that if a vertex subset S covers E-C(G) such that vertical bar V (G)vertical bar >= 2 vertical bar S vertical bar + 1, then G - S is not connected. Finally, we provide tight upper bounds for the order, size and number of non-trivial components of G-S (components having more than one vertex) in terms of vertical bar S vertical bar, and characterize all the extremal graphs.
引用
收藏
页码:309 / 318
页数:10
相关论文
共 6 条