Non-separating subgraphs in highly connected graphs
Non-separating subgraphs in highly connected graphs
复制标题
高度连通图中的非分离子图
DOI：
10.1016/j.jctb.2015.12.001
复制
发表时间：
2016
影响因子：
1.4
通讯作者：
Ken-ichi Kawarabayashi
中科院分区：
文献类型：
--
作者：
Shinya Fujita;Ken-ichi Kawarabayashi
Quarassen的一个著名的猜想是：任何（a+ B+ 1）-连通图，当a≥ B时，都可以分解为两部分A和B，使得A是a-连通的，B是b-连通的. B= 2的情况是解决了他自己，但猜想仍然是开放的B≥ 3。受此启发，我们证明了每个k-连通图G（k≥ 4）都有一个子图M使得1. M是3-连通的，至多5个顶点（因此G− V（M）是（k− 5）-连通的），或2。M是一个诱导圈，使得G− V（C）是（k− 2）-连通的。这一结果改进了Egawa和Kawarabayashi的已有结果。我们的结果也与马德尔关于临界k-连通图的结果和问题有关。部分回答了马德尔在1988年提出的问题。
A well-known conjecture of Thomassen says that every (a+ b+ 1)-connected graph with a≥ b can be decomposed into two parts A and B such that A is a-connected and B is b-connected. The case b= 2 is settled by Thomassen himself, but the conjecture is still open for b≥ 3. Motivated by this, we prove that every k-connected graph G (with k≥ 4) has a subgraph M such that either 1. M is 3-connected with at most 5 vertices (thus G− V (M) is (k− 5)-connected), or 2. M is an induced cycle such that G− V (C) is (k− 2)-connected. This result improves previous known results by Egawa and Kawarabayashi, respectively. Our result is also related to results and questions of Mader concerning critically k-connected graphs. We partially answer the question of Mader in 1988.