机构:
Univ Hamburg, Math Seminar, Bundesstr 55, D-20146 Hamburg, GermanyUniv Hamburg, Math Seminar, Bundesstr 55, D-20146 Hamburg, Germany
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.