Note on non-separating and removable cycles in highly connected graphs |
| |
| Authors: | Shinya Fujita Ken-ichi Kawarabayashi |
| |
| Institution: | a Department of Mathematics, Gunma National College of Technology, Maebashi, Gunma 371-8530, Japan
b National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan |
| |
| Abstract: | We combine two well-known results by Mader and Thomassen, respectively. Namely, we prove that for any k-connected graph G (k≥4), there is an induced cycle C such that G−V(C) is (k−3)-connected and G−E(C) is (k−2)-connected. Both “(k−3)-connected” and “(k−2)-connected” are best possible in a sense. |
| |
| Keywords: | Non-separating subgraph Highly connected graph |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
